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