Basic tree transducers (Q579951)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Basic tree transducers |
scientific article; zbMATH DE number 4016219
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Basic tree transducers |
scientific article; zbMATH DE number 4016219 |
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
