Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426757 | Information and Computation | 2014 | 11 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Zuzana Bednárová, Viliam Geffert, Carlo Mereghetti, Beatrice Palano,