We study the size-cost of Boolean operations on constant height nondeterministic pushdown automata, i.e. on pushdown automata with a constant limit on the size of the pushdown. For intersection, we show an exponential simulation and prove that the exponential blow-up is necessary. For union, instead, we provide a linear trade-off while, for complement, we show a double-exponential simulation and prove a single-exponential lower bound.
Boolean language operations on nondeterministic automata with a pushdown of constant height / V. Geffert, Z. Bednárová, C. Mereghetti, B. Palano (LECTURE NOTES IN COMPUTER SCIENCE). - In: Computer Science : Theory and Applications / [a cura di] A.A. Bulatov, A.M. Shur. - Berlin : Springer, 2013. - ISBN 9783642385353. - pp. 100-111 (( Intervento presentato al 13. convegno International Computer Science Symposium in Russia tenutosi a Ekaterinburg nel 2013 [10.1007/978-3-642-38536-0_9].
Boolean language operations on nondeterministic automata with a pushdown of constant height
C. Mereghetti;B. Palano
2013
Abstract
We study the size-cost of Boolean operations on constant height nondeterministic pushdown automata, i.e. on pushdown automata with a constant limit on the size of the pushdown. For intersection, we show an exponential simulation and prove that the exponential blow-up is necessary. For union, instead, we provide a linear trade-off while, for complement, we show a double-exponential simulation and prove a single-exponential lower bound.
| File | Dimensione | Formato | |
|---|---|---|---|
|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
271.27 kB
Formato
Adobe PDF
|
271.27 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.
