Two double-exponential gaps for automata with a limited pushdown

DOI10.1016/j.ic.2016.06.005zbMath1370.68157OpenAlexW2414151754WikidataQ115574502 ScholiaQ115574502MaRDI QIDQ515677

Viliam Geffert, Zuzana Bednárová

Publication date: 16 March 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2016.06.005

zbMATH Keywords

regular languagespushdown automatadescriptional complexityfinite state automatatwo-way automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

Pushdown automata and constant height: decidability and bounds

Cites Work

• The size-cost of Boolean operations on constant height deterministic pushdown automata
• The Boolean closure of linear context-free languages
• More concise representation of regular languages by automata and regular expressions
• Complexity measures for regular expressions
• The state complexities of some basic operations on regular languages
• Language operations with regular expressions of polynomial size
• Queue Automata of Constant Length
• Removing Nondeterminism in Constant Height Pushdown Automata
• Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height
• Nondeterminism and the size of two way finite automata
• Mathematical Foundations of Computer Science 2005
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• On context-free languages and push-down automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Two double-exponential gaps for automata with a limited pushdown