Two-way nondeterministic pushdown automata (2PDA) are classical nondeterministic pushdown automata (PDA) enhanced with two-way motion of the input head. In this paper, the subclass of 2PDA 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 and pushdown 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: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 449(2012), pp. 119-133.
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; bounded pushdown reversals; descriptional complexity; two-way pushdown automata |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Data di pubblicazione: | 2012 |
Rivista: | |
Tipologia: | Article (author) |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.tcs.2012.04.007 |
Appare nelle tipologie: | 01 - Articolo su periodico |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
pubblicato.pdf | Publisher's version/PDF | Administrator Richiedi una copia |