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.
EnglishIt is well known that the pushdown store language P(M) of a pushdown automaton (PDA) M — i.e., the language consisting of words occurring on the pushdown along accepting computations of M — is a regular language. Here, we design succinct nondeterministic finite automata (NFA) accepting P(M). In detail, an upper bound on the size of an NFA for P(M) is obtained, which is quadratic in the number of states and linear in the number of pushdown symbols of M. Moreover, this upper bound is shown to be asymptotically optimal. Then, several restricted variants of PDA are considered, leading to improved constructions. In all cases, we prove the asymptotical optimality of the size of the resulting NFA. Finally, we apply our results to decidability questions related to PDA, and obtain solutions in deterministic polynomial time.
| Titolo: | Descriptional complexity of pushdown store languages |
| Autori: | MEREGHETTI, CARLO (Penultimo) PALANO, BEATRICE SANTA (Ultimo) |
| Parole Chiave: | decidability questions; descriptional complexity; pushdown automata; pushdown store languages |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
| Data di pubblicazione: | 2012 |
| Digital Object Identifier (DOI): | 10.1007/978-3-642-31623-4_16 |
| 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/194628
Copyright © 2020