The power of extended top-down tree transducers
- Extended top-down tree transducers (transducteurs generalises descendants; see [A. Arnold and M. Dauchet, Bi- transductions de forets, 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.
| Author details: | Andreas Maletti, Jonathan Graehl, Mark Hopkins, Kevin Knight |
|---|---|
| URL: | http://epubs.siam.org/SICOMP/ |
| DOI: | https://doi.org/10.1137/070699160 |
| ISSN: | 0097-5397 |
| Publication type: | Article |
| Language: | English |
| Year of first publication: | 2009 |
| Publication year: | 2009 |
| Release date: | 2017/03/25 |
| Source: | Siam journal on computing. - ISSN 0097-5397. - 39 (2009), 2, S. 410 - 430 |
| Organizational units: | Humanwissenschaftliche Fakultät / Strukturbereich Kognitionswissenschaften / Department Linguistik |
| Peer review: | Referiert |
