Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals

DOI10.1007/978-3-642-22600-7_20zbMath1341.68100MaRDI QIDQ5200096

Beatrice Palano, Andreas Malcher, Carlo Mereghetti

Publication date: 29 July 2011

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22600-7_20

zbMATH Keywords

bounded languages; descriptional complexity; bounded head reversals; two-way pushdown automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of multi-head finite automata: origins and directions
• More concise representation of regular languages by automata and regular expressions
• 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
• Reversal-bounded multipushdown machines
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
• 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