Descriptional complexity of two-way pushdown automata with restricted head reversals

DOI10.1016/j.tcs.2012.04.007zbMath1276.68094OpenAlexW2031307533MaRDI QIDQ443747

Carlo Mereghetti, Andreas Malcher, Beatrice Palano

Publication date: 13 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.04.007

zbMATH Keywords

bounded languagesdescriptional complexitybounded head reversalsbounded pushdown reversalstwo-way pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (10)

Boolean language operations on nondeterministic automata with a pushdown of constant height ⋮ Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers* ⋮ Sweeping input-driven pushdown automata ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ Removing nondeterminism in constant height pushdown automata ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ The descriptional power of queue automata of constant length ⋮ Descriptional complexity of iterated uniform finite-state transducers ⋮ Deterministic input-driven queue automata: finite turns, decidability, and closure properties ⋮ Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of multi-head finite automata: origins and directions
• Deterministic two-way one-head pushdown automata are very powerful
• More concise representation of regular languages by automata and regular expressions
• A note on bounded-reversal multipushdown machines
• Finite automata and unary languages
• Simple counter machines and number-theoretic problems
• The complexity of the equivalence problem for two characterizations of Presburger sets
• Succinct representation of regular languages by Boolean automata
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• A remark on middle space bounded alternating Turing machines
• Converting two-way nondeterministic unary automata into simpler automata.
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
• Optimal Simulations between Unary Automata
• Behaviours of Unary Quantum Automata
• The Complexity of Regular(-Like) Expressions
• On the Succinctness of Different Representations of Languages
• Regularity and Related Problems for Deterministic Pushdown Automata
• A note on the succinctness of descriptions of deterministic languages
• New Decidability Results Concerning Two-Way Counter Machines
• Descriptional Complexity of Bounded Context-Free Languages
• Classes of Recursively Enumerable Sets and Their Decision Problems

This page was built for publication: Descriptional complexity of two-way pushdown automata with restricted head reversals