We study the descriptional cost of removing nondeterminism in constant height pushdown automata - i.e., pushdown automata with a built-in constant limit on the height of the pushdown. We show a double-exponential size increase when converting a constant height nondeterministic pushdown automaton into an equivalent deterministic device. Moreover, we prove that such a double-exponential blow-up cannot be avoided by certifying its optimality. As a direct consequence, we get that eliminating nondeterminism in classical finite state automata is single-exponential even with the help of a constant height pushdown store.
Removing nondeterminism in constant height pushdown automata / Z. Bednárová, V. Geffert, C. Mereghetti, B. Palano. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 237(2014 Oct), pp. 257-267. [10.1016/j.ic.2014.03.002]
Removing nondeterminism in constant height pushdown automata
C. Mereghetti
;B. PalanoUltimo
2014
Abstract
We study the descriptional cost of removing nondeterminism in constant height pushdown automata - i.e., pushdown automata with a built-in constant limit on the height of the pushdown. We show a double-exponential size increase when converting a constant height nondeterministic pushdown automaton into an equivalent deterministic device. Moreover, we prove that such a double-exponential blow-up cannot be avoided by certifying its optimality. As a direct consequence, we get that eliminating nondeterminism in classical finite state automata is single-exponential even with the help of a constant height pushdown store.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
482.92 kB
Formato
Adobe PDF
|
482.92 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.