The Power of Extended Top-Down Tree Transducers
Authors:
- Andreas MalettiAMAndreas Maletti
- Jonathan GraehlJGJonathan Graehl
- Mark HopkinsMHMark Hopkins
- Kevin KnightKKKevin Knight
- 1 January 2009
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 39 (2) , 410-430
Abstract
Extended top-down tree transducers (transducteurs généralisés descendants; see [A. Arnold and M. Dauchet, Bi-transductions de forêts, in Proceedings of the 3rd International Colloquium on Automata, Languages and Programming, Edinburgh University Press, Edinburgh, 1976, pp. 74–86]) received renewed interest in the field of natural language processing. Here those transducers are extensively and systematically studied. Their main properties are identified and their relation to classical top-down tree transducers is exactly characterized. The obtained properties completely explain the Hasse diagram of the induced classes of tree transformations. In addition, it is shown that most interesting classes of transformations computed by extended top-down tree transducers are not closed under composition.Keywords
This publication has 17 references indexed in Scilit:
- Compositions of extended top-down tree transducersInformation and Computation, 2008
- Modular tree transducersTheoretical Computer Science, 1991
- Macro tree transducersJournal of Computer and System Sciences, 1985
- Morphismes et bimorphismes d'arbresTheoretical Computer Science, 1982
- Attribute grammars and recursive program schemes ITheoretical Computer Science, 1982
- Attribute grammars and recursive program schemes IITheoretical Computer Science, 1982
- Three hierarchies of transducersTheory of Computing Systems, 1981
- Composition of top-down and bottom-up tree transductionsInformation and Control, 1979
- Top-down tree transducers with regular look-aheadTheory of Computing Systems, 1976
- Bottom-up and top-down tree transformations— a comparisonTheory of Computing Systems, 1975