The size-cost of Boolean operations on constant height deterministic pushdown automata

DOI10.1016/j.tcs.2012.05.009zbMath1272.68205MaRDI QIDQ443731

Beatrice Palano, Viliam Geffert, Zuzana Bednárová, Carlo Mereghetti

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.05.009

zbMATH Keywords

regular languages; pushdown automata; finite state automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q19: Descriptive complexity and finite models

Related Items

Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*, Descriptional complexity of iterated uniform finite-state transducers, Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata, Alternating space is closed under complement and other simulations for sublogarithmic space, Two double-exponential gaps for automata with a limited pushdown, The descriptional power of queue automata of constant length, Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power, Removing nondeterminism in constant height pushdown automata, Boolean language operations on nondeterministic automata with a pushdown of constant height

Cites Work

• Unnamed Item
• 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
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES