Two double-exponential gaps for automata with a limited pushdown

DOI10.1016/J.IC.2016.06.005zbMATH Open1370.68157OpenAlexW2414151754WikidataQ115574502 ScholiaQ115574502MaRDI QIDQ515677FDOQ515677

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

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

zbMATH Keywords

descriptional complexitypushdown automatafinite state automataregular languagestwo-way automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

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

Cited In (5)

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

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)