Boolean language operations on nondeterministic automata with a pushdown of constant height

Geffert, V.; Bednárová, Z.; Mereghetti, C.; Palano, B.

doi:10.1007/978-3-642-38536-0_9

IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca

IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.

AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.

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:	V. Geffert Z. Bednárová MEREGHETTI, CARLO PALANO, BEATRICE SANTA mostra contributor esterni nascondi contributor esterni
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

Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/2434/231662

Citazioni

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.