Iterated stack automata and complexity classes
From MaRDI portal
Publication:1183602
DOI10.1016/0890-5401(91)90015-TzbMath0758.68029OpenAlexW1992878210MaRDI QIDQ1183602
Publication date: 28 June 1992
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(91)90015-t
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (19)
The grammar of mammalian brain capacity ⋮ Transducers and the decidability of independence in free monoids ⋮ The Caucal hierarchy: interpretations in the (W)MSO+\(\mathsf{U}\) logic ⋮ Corrigendum to: ``Iterated stack automata and complexity classes ⋮ New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines ⋮ Unnamed Item ⋮ Tree-stack automata ⋮ Emptiness of Multi-pushdown Automata Is 2ETIME-Complete ⋮ Parity to Safety in Polynomial Time for Pushdown and Collapsible Pushdown Systems ⋮ Emptiness of Ordered Multi-Pushdown Automata is 2ETIME-Complete ⋮ Iterated pushdown automata and sequences of rational numbers ⋮ Weighted automata with storage ⋮ On store languages of language acceptors ⋮ Unnamed Item ⋮ Decidability of the finiteness of ranges of tree transductions ⋮ Principal abstract families of weighted tree languages ⋮ Regular sets over extended tree structures ⋮ The IO and OI hierarchies revisited ⋮ Output string languages of compositions of deterministic macro tree transducers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Look-ahead on pushdowns
- Extended macro grammars and stack controlled machines
- Two-way automata with more than one storage medium
- Pushdown machines for the macro tree transducer
- High level tree transducers and iterated pushdown tree transducers
- The OI-hierarchy is closed under control
- Tree transducers, L systems, and two-way machines
- Tree-size bounded alternation
- The IO- and OI-hierarchies
- Two-way A-transducers and AFL
- Hierarchies of complete problems
- Space-bounded reducibility among combinatorial problems
- Two-way nested stack automata are equivalent to two-way stack automata
- Complete problems for deterministic polynomial time
- A generalized approach to formal languages
- One way finite visit automata
- IO and OI. II
- Hierarchy theorems for two-way finite state transducers
- Some definitional suggestions for automata theory
- Nonerasing stack automata
- Checking automata and one-way stack languages
- Proof of correctness of data representations
- Absolutely parallel grammars and two-way finite-state transducers
- Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
- Alternating Pushdown and Stack Automata
- An automata-theoretical characterization of the OI-hierarchy
- Iterated linear control and iterated one-turn pushdowns
- Stack Machines and Classes of Nonnested Macro Languages
- On deterministic indexed languages
- Alternation
- On the complexity of finite, pushdown, and stack automata
- Controlled iteration grammars and full hyper-AFL's
- Visits, crosses, and reversals for nondeterministic off-line machines
- Three hierarchies of transducers
- An Approach to a Unified Theory of Automata
- One-way stack automata
- Indexed Grammars—An Extension of Context-Free Grammars
- Nested Stack Automata
- Full AFLs and nested iterated substitution
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
This page was built for publication: Iterated stack automata and complexity classes
