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

DOI10.1016/J.TCS.2012.05.009zbMath1272.68205OpenAlexW2177633274MaRDI 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 languagespushdown automatafinite state automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive complexity and finite models (68Q19)

Related Items (9)

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

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

This page was built for publication: The size-cost of Boolean operations on constant height deterministic pushdown automata