TREES, TRANSDUCERS, AND TRANSFORMATIONS,
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1968
- Accession Number
- AD0681174
Entities
People
- William Chesley Rounds
Organizations
- Stanford University