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

DOI10.1016/j.tcs.2012.04.007zbMath1276.68094MaRDI 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 languages; descriptional complexity; bounded head reversals; bounded pushdown reversals; two-way pushdown automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

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

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