Basic tree transducers

摘要

The concept of basic tree transducer is investigated; it is obtained as a natural restriction of the concept of macro tree transducer by forbidding nesting of states. Basic tree transducers are characterized in terms of one-turn pushdown machines. A close connection between path languages of ranges of (compositions of) basic tree transducers and (iterated) control on linear grammars is established. This connection allows to prove the strictness of the composition hierarchy of basic tree transducers.