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.
The size cost of boolean operations on constant height deterministic pushdown automata / Z. Bednarova, V. Geffert, C. Mereghetti, B. Palano - In: Descriptional Complexity of Formal Systems / [a cura di] M. Holzer, M. Kutrib, G. Pighizzini. - Berlin : Springer, 2011. - ISBN 9783642225994. - pp. 80-92 (( Intervento presentato al 13. convegno International Workshop on Descriptional complexity of Formal Systems tenutosi a Limberg nel 2011.
The size cost of boolean operations on constant height deterministic pushdown automata
C. MereghettiPenultimo
;B. PalanoUltimo
2011
Abstract
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
244.66 kB
Formato
Adobe PDF
|
244.66 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
