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 - 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.
Titolo: | Boolean language operations on nondeterministic automata with a pushdown of constant height |
Autori: | |
Parole Chiave: | descriptional complexity; finite state automata; nondeterministic pushdown automata; regular languages |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Data di pubblicazione: | 2013 |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/978-3-642-38536-0_9 |
Tipologia: | Book Part (author) |
Appare nelle tipologie: | 03 - Contributo in volume |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
pubblicato.pdf | Publisher's version/PDF | Administrator Richiedi una copia |