Accession Number : AD0681174

Title :   TREES, TRANSDUCERS, AND TRANSFORMATIONS,

Corporate Author : STANFORD UNIV CALIF DEPT OF MATHEMATICS

Personal Author(s) : Rounds,William Chesley

Report Date : AUG 1968

Pagination or Media Count : 90

Abstract : The paper is an application of generalized finite automata theory to the theory of transformational grammars. Using a tree automaton with outputs, we obtain a simple analogue of the transformation mapping. A tree transducer works in analogy with a (partial) generalized sequential machine in that it has local outputs and state transitions. It differs from such a machine in that its inputs and outputs are trees instead of strings. It also differs from a tree automaton in that it starts at the root (top) of its input tree and works toward the branches. It thus reverses the action of a tree automaton. The main result is that languages so defined are recursive; thus one has a manageable extension of the context-free languages. We show how some transformations proposed for English can be formalized, and we discuss parsing problems in our model. We also have several theoretic results. Transformational mappings are closed under composition, for example, and the domain of a partial mapping is always a regular set of trees (thus we have a 'top-down' characterization of regular sets.) We discuss the close relationship of tree transducers with indexed context-free grammars. (Author)

Descriptors :   (*ARTIFICIAL INTELLIGENCE, AUTOMATA), (*TRANSFORMATIONAL GRAMMARS, TOPOLOGY), CONTEXT FREE GRAMMARS, ENGLISH LANGUAGE, SYNTAX, LEARNING MACHINES, SET THEORY

Subject Categories : Linguistics
      Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE