2011 | OriginalPaper | Buchkapitel
The Size-Cost of Boolean Operations on Constant Height Deterministic Pushdown Automata
verfasst von : Zuzana Bednárová, Viliam Geffert, Carlo Mereghetti, Beatrice Palano
Erschienen in: Descriptional Complexity of Formal Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the size-cost of boolean operations on
constant height deterministic pushdown automata
. We prove an
asymptotically optimal
exponential blow-up for union and intersection, as well as polynomial blow-up for complement.