The OI-hierarchy is closed under control
From MaRDI portal
Publication:1109578
DOI10.1016/0890-5401(88)90026-0zbMath0655.68103OpenAlexW2028265262MaRDI QIDQ1109578
Publication date: 1988
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(88)90026-0
Related Items
High level tree transducers and iterated pushdown tree transducers ⋮ Iterated stack automata and complexity classes ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Decidability of the finiteness of ranges of tree transductions ⋮ Output string languages of compositions of deterministic macro tree transducers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear indexed languages
- Pushdown machines for the macro tree transducer
- Tree transducers, L systems, and two-way machines
- The IO- and OI-hierarchies
- A geometric hierarchy of languages
- EOL systems with control devices
- Surface tree languages and parallel derivation trees
- Control sets on context-free grammar forms
- IO and OI. II
- An automata-theoretical characterization of the OI-hierarchy
- Iterated linear control and iterated one-turn pushdowns
- Extension of tabled 0L-systems and languages
- On some families of languages related to developmental systems
- TOL schemes and control sets
- Control sets on linear grammars
- Controlled iteration grammars and full hyper-AFL's
- Three hierarchies of transducers
- Control sets on grammars
- Indexed Grammars—An Extension of Context-Free Grammars
- Full AFLs and nested iterated substitution
