The Size-Cost of Boolean Operations on Constant Height Deterministic Pushdown Automata

DOI10.1007/978-3-642-22600-7_7zbMath1341.68076OpenAlexW2130333463MaRDI QIDQ5200083

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

Publication date: 29 July 2011

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22600-7_7

zbMATH Keywords

pushdown automatadescriptional complexityBoolean operations on languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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