It 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.

Descriptional complexity of pushdown store languages / A. Malcher, K. Meckel, C. Mereghetti, B. Palano (LECTURE NOTES IN COMPUTER SCIENCE). - In: Descriptional Complexity of Formal Systems / [a cura di] M. Kutrib, N. Moreira, R. Reis. - Berlin : Springer, 2012. - ISBN 9783642316227. - pp. 209-221 (( Intervento presentato al 14. convegno International Workshop on Descriptional Complexity of Formal Systems tenutosi a Braga nel 2012 [10.1007/978-3-642-31623-4_16].

Descriptional complexity of pushdown store languages

C. Mereghetti
Penultimo
;
B. Palano
Ultimo
2012

Abstract

It 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.
decidability questions; descriptional complexity; pushdown automata; pushdown store languages
Settore INF/01 - Informatica
2012
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
pubblicato.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 246.24 kB
Formato Adobe PDF
246.24 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/194628
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact