Basic tree transducers (Q579951)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Basic tree transducers |
scientific article |
Statements
Basic tree transducers (English)
0 references
1987
0 references
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.
0 references
basic tree transducer
0 references
pushdown machines
0 references
path languages
0 references
control on linear grammars
0 references
0 references
