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.
descriptional complexity; finite state automata; nondeterministic pushdown automata; regular languages
Settore INF/01 - Informatica
2013
Book Part (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/231662
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? ND
social impact