Removing nondeterminism in constant height pushdown automata
From MaRDI portal
Publication:2252532
DOI10.1016/j.ic.2014.03.002zbMath1360.68539OpenAlexW2029779257MaRDI QIDQ2252532
Zuzana Bednárová, Beatrice Palano, Viliam Geffert, Carlo Mereghetti
Publication date: 18 July 2014
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2014.03.002
regular languagesdescriptional complexityfinite state automatadeterministic and nondeterministic pushdown automata
Related Items (6)
Boolean language operations on nondeterministic automata with a pushdown of constant height ⋮ Unnamed Item ⋮ Pushdown automata and constant height: decidability and bounds ⋮ The descriptional power of queue automata of constant length ⋮ Descriptional complexity of iterated uniform finite-state transducers ⋮ Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The size-cost of Boolean operations on constant height deterministic pushdown automata
- Descriptional complexity of two-way pushdown automata with restricted head reversals
- More concise representation of regular languages by automata and regular expressions
- Simple counter machines and number-theoretic problems
- Space bounded computations: Review and new separation results
- Converting two-way nondeterministic unary automata into simpler automata.
- Algorithmics for hard problems.
- Complementing two-way finite automata
- Optimal Simulations between Unary Automata
- Queue Automata of Constant Length
- Behaviours of Unary Quantum Automata
- Quantum Computation and Quantum Information
- Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
- Size Complexity of Two-Way Finite Automata
- Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height
- Two Double-Exponential Gaps for Automata with a Limited Pushdown
- One-way stack automata
- Trace monoids with idempotent generators and measure-only quantum automata
This page was built for publication: Removing nondeterminism in constant height pushdown automata
