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

DOI10.1016/J.TCS.2012.05.009MaRDI QIDQ443731zbMATH OpenOpenAlexFDO

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

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

finite state automatapushdown automataregular languages

Mathematics Subject Classification ID

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

Recommendations

• The size-cost of Boolean operations on constant height deterministic pushdown automata
• Boolean language operations on nondeterministic automata with a pushdown of constant height
• Boolean language operations on nondeterministic automata with a pushdown of constant height
• Pushdown automata and constant height: decidability and bounds
• Pushdown automata and constant height: decidability and bounds
• On the complexity of membership and counting in height-deterministic pushdown automata
• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• Efficient determinization of visibly and height-deterministic pushdown automata
• On The Space Complexity Of Turn Bounded Pushdown Automata
• On the size of binary decision diagrams representing Boolean functions

Cites work

• Complexity measures for regular expressions
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• Language operations with regular expressions of polynomial size
• More concise representation of regular languages by automata and regular expressions
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• The Boolean closure of linear context-free languages
• The state complexities of some basic operations on regular languages

Cited in

(14)

• The descriptional power of queue automata of constant length
• Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power
• Pushdown automata and constant height: decidability and bounds
• Removing nondeterminism in constant height pushdown automata
• Boolean language operations on nondeterministic automata with a pushdown of constant height
• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• 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
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• Non-self-embedding grammars, constant-height pushdown automata, and limited automata
• Descriptional complexity of iterated uniform finite-state transducers
• Pushdown automata and constant height: decidability and bounds

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

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