Basic tree transducers (Q579951): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
| Property / review text | |||
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. | |||
| Property / review text: 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. / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 68Q45 / rank | |||
Normal rank | |||
| Property / zbMATH DE Number | |||
| Property / zbMATH DE Number: 4016219 / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
basic tree transducer | |||
| Property / zbMATH Keywords: basic tree transducer / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
pushdown machines | |||
| Property / zbMATH Keywords: pushdown machines / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
path languages | |||
| Property / zbMATH Keywords: path languages / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
control on linear grammars | |||
| Property / zbMATH Keywords: control on linear grammars / rank | |||
Normal rank | |||
Revision as of 17:33, 1 July 2023
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
