
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 contextfree 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 'topdown' characterization of regular sets.) We discuss the close relationship of tree transducers with indexed contextfree 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