Output String Languages of Compositions of Deterministic Macro Tree Transducers
✍ Scribed by Joost Engelfriet; Sebastian Maneth
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 376 KB
- Volume
- 64
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
The composition of total deterministic macro tree transducers gives rise to a proper hierarchy with respect to their output string languages (these are the languages obtained by taking the yields of the output trees). There is a language not in this hierarchy which can be generated by a (quite restricted) nondeterministic string transducer, namely, a two-way generalized sequential machine. Similar results hold for attributed tree transducers, for controlled EDT0L systems, and for YIELD mappings (which proves properness of the IO-hierarchy). Witnesses for the properness of the macro tree transducer hierarchy can already be found in the latter three hierarchies.