We study the cost of Boolean operations on constant height nondeterministic pushdown automata, i.e., on the ordinary pushdown automata with a limit on the size of the pushdown. For intersection, we show an exponential simulation and prove that the exponential blow-up is necessary in the worst case. 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. The same gaps for Boolean operations with regular languages have been shown for traditional nondeterministic automata with unrestricted pushdown.
Boolean language operations on nondeterministic automata with a pushdown of constant height / Z. Bednárová, V. Geffert, C. Mereghetti, B.S. Palano. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - 90(2017), pp. 99-114. [10.1016/j.jcss.2017.06.007]
Boolean language operations on nondeterministic automata with a pushdown of constant height
C. Mereghetti;B.S. Palano
2017
Abstract
We study the cost of Boolean operations on constant height nondeterministic pushdown automata, i.e., on the ordinary pushdown automata with a limit on the size of the pushdown. For intersection, we show an exponential simulation and prove that the exponential blow-up is necessary in the worst case. 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. The same gaps for Boolean operations with regular languages have been shown for traditional nondeterministic automata with unrestricted pushdown.File | Dimensione | Formato | |
---|---|---|---|
1-s2.0-S0022000017301071-main.pdf
accesso riservato
Descrizione: Articolo principale
Tipologia:
Publisher's version/PDF
Dimensione
928.52 kB
Formato
Adobe PDF
|
928.52 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.