Two double-exponential gaps for automata with a limited pushdown

DOI10.1016/J.IC.2016.06.005MaRDI QIDQ515677zbMATHOpenAlexWikidataFDO

Authors Zuzana Bednárová, Viliam Geffert

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

descriptional complexitypushdown automatafinite state automataregular languagestwo-way automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Two double-exponential gaps for automata with a limited pushdown
• Removing nondeterminism in constant height pushdown automata
• Removing nondeterminism in constant height pushdown automata
• Limited automata and context-free languages
• Boolean language operations on nondeterministic automata with a pushdown of constant height

Cites work

• scientific article; zbMATH DE number 6515829 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Boolean language operations on nondeterministic automata with a pushdown of constant height
• Complexity measures for regular expressions
• Language operations with regular expressions of polynomial size
• Mathematical Foundations of Computer Science 2005
• More concise representation of regular languages by automata and regular expressions
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Nondeterminism and the size of two way finite automata
• On context-free languages and push-down automata
• Queue automata of constant length
• Removing nondeterminism in constant height pushdown automata
• The Boolean closure of linear context-free languages
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• The state complexities of some basic operations on regular languages

Cited in

(5)

• Two double-exponential gaps for automata with a limited pushdown
• An Infinite Automaton Characterization of Double Exponential Time
• Pushdown automata and constant height: decidability and bounds
• Removing nondeterminism in constant height pushdown automata
• Removing nondeterminism in constant height pushdown automata

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q515677)