We design succinct nondeterministic finite automata accepting pushdown store languages — i.e., the languages consisting of the pushdown contents along accepting computations of pushdown automata. Then, several restricted variants of pushdown automata are considered, leading to improved constructions. Finally, we apply our results to decidability questions related to pushdown automata

On pushdown store languages / A. Malcher, K. Meckel, C. Mereghetti, B. Palano - In: Italian conference on theoretical computer science : proceeedings[s.l] : Università degli Studi di Varese, 2012. - pp. 168-171 (( Intervento presentato al 13. convegno ICTCS tenutosi a Varese nel 2012.

On pushdown store languages

C. Mereghetti;B. Palano
2012

Abstract

We design succinct nondeterministic finite automata accepting pushdown store languages — i.e., the languages consisting of the pushdown contents along accepting computations of pushdown automata. Then, several restricted variants of pushdown automata are considered, leading to improved constructions. Finally, we apply our results to decidability questions related to pushdown automata
pushdown automata; pushdown store languages
Settore INF/01 - Informatica
2012
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
ictcs12.pdf

accesso riservato

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 251.64 kB
Formato Adobe PDF
251.64 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/449309
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact