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.
EnglishWe 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.
| 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): | 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 |
http://hdl.handle.net/2434/231662
Copyright © 2020