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.
EnglishTwo-way nondeterministic pushdown automata (2PDA2PDA) are classical nondeterministic pushdown automata (PDAPDA) enhanced with two-way motion of the input head. In this paper, the subclass of 2PDA2PDA accepting bounded languages and making at most a constant number of input head turns is studied with respect to descriptional complexity aspects. In particular, the effect of reducing the number of pushdown reversals to a constant number is of interest. It turns out that this reduction leads to an exponential blow-up in case of nondeterministic devices, and to a doubly-exponential blow-up in case of deterministic devices. If the restriction on boundedness of the languages considered and on the finiteness of the number of head turns is dropped, the resulting trade-offs are no longer bounded by recursive functions, and so-called non-recursive trade-offs are shown.
Descriptional complexity of two-way pushdown automata with restricted head reversals / A. Malcher, C. Mereghetti, B. Palano - In: Descriptional Complexity of Formal Systems / [a cura di] M. Holzer, M. Kutrib, G. Pighizzini. - Berlin : Springer, 2011. - ISBN 9783642225994. - pp. 248-260 (( Intervento presentato al 13. convegno International Workshop on Descriptional Complexity of Formal Systems tenutosi a Limburg nel 2011.
| Titolo: | Descriptional complexity of two-way pushdown automata with restricted head reversals |
| Autori: | MEREGHETTI, CARLO (Secondo) PALANO, BEATRICE SANTA (Ultimo) |
| Parole Chiave: | bounded head reversals; bounded languages; descriptional complexity; two-way pushdown automata |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
| Data di pubblicazione: | 2011 |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/978-3-642-22600-7_20 |
| 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/160705
Copyright © 2021