Removing nondeterminism in constant height pushdown automata

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

zbMATH Keywords

regular languagesdescriptional complexityfinite state automatadeterministic and nondeterministic pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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