We study the descriptional cost of converting constant height nondeterministic pushdown automata into equivalent deterministic devices. We show a double-exponential upper bound for this conversion, together with a super-exponential lower bound.
Removing nondeterminism in constant height pushdown automata / Z. Bednarova, V. Geffert, 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. 76-88 (( Intervento presentato al 14. convegno International Workshop on Descriptional Complexity of Formal Systems (DCFS) tenutosi a Braga nel 2012 [10.1007/978-3-642-31623-4_6].
Removing nondeterminism in constant height pushdown automata
C. MereghettiPenultimo
;B. PalanoUltimo
2012
Abstract
We study the descriptional cost of converting constant height nondeterministic pushdown automata into equivalent deterministic devices. We show a double-exponential upper bound for this conversion, together with a super-exponential lower bound.
| File | Dimensione | Formato | |
|---|---|---|---|
|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
272.04 kB
Formato
Adobe PDF
|
272.04 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.
