Basic tree transducers
From MaRDI portal
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.
Recommendations
Cites work
- A geometric hierarchy of languages
- A representation of trees by languages. II
- An automata-theoretical characterization of the OI-hierarchy
- Attribute grammars and recursive program schemes. I. II
- Bottom-up and top-down tree transformations— a comparison
- Bounded nesting in macro grammars
- Checking automata and one-way stack languages
- Control sets on context-free grammar forms
- Control sets on grammars
- Control sets on linear grammars
- Extended macro grammars and stack controlled machines
- Extension of tabled 0L-systems and languages
- Finite-Turn Pushdown Automata
- Full AFLs and nested iterated substitution
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Generalized sequential machine maps
- scientific article; zbMATH DE number 3917739 (Why is no real title available?)
- scientific article; zbMATH DE number 3972227 (Why is no real title available?)
- scientific article; zbMATH DE number 3750335 (Why is no real title available?)
- scientific article; zbMATH DE number 3459894 (Why is no real title available?)
- scientific article; zbMATH DE number 3509706 (Why is no real title available?)
- scientific article; zbMATH DE number 3569855 (Why is no real title available?)
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 3997179 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- scientific article; zbMATH DE number 3413820 (Why is no real title available?)
- Indexed Grammars—An Extension of Context-Free Grammars
- IO and OI. II
- Linear indexed languages
- Look-ahead on pushdowns
- Macro tree transducers
- Mappings and grammars on trees
- Nested Stack Automata
- On the equivalence problem for attribute systems
- One way finite visit automata
- Pushdown machines for the macro tree transducer
- Pushdown tree automata
- Stack Machines and Classes of Nonnested Macro Languages
- The IO- and OI-hierarchies
- Three hierarchies of transducers
- Top-down tree transducers with regular look-ahead
- Tree transducers, L systems, and two-way machines
Cited in
(10)- Extended macro grammars and stack controlled machines
- scientific article; zbMATH DE number 3945364 (Why is no real title available?)
- scientific article; zbMATH DE number 3965457 (Why is no real title available?)
- scientific article; zbMATH DE number 3972227 (Why is no real title available?)
- scientific article; zbMATH DE number 2040925 (Why is no real title available?)
- Composition closure of -free linear extended top-down tree transducers
- Tree transducers, L systems and two-way machines (extended abstract)
- Input strictly local tree transducers
- Modular tree transducers
- A complete rewriting system for a monoid of tree transformation classes
This page was built for publication: Basic tree transducers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q579951)
