Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333006 | Journal of Computer and System Sciences | 2005 | 27 Pages |
Abstract
The amount of nondeterminism that a pushdown automaton requires to recognize an input string can be measured by the minimum number of guesses that it must make to accept the string, where guesses are measured in bits of information. When this quantity is unbounded, the rate at which it grows as the length of the string increases serves as a measure of the pushdown automaton's “rate of consumption” of nondeterminism. We show that this measure is similar to other complexity measures in that it gives rise to an infinite hierarchy of complexity classes of context-free languages differing in the amount of the resource (in this case, nondeterminism) that they require. In addition, we show that there are context-free languages that can only be recognized by a pushdown automaton whose nondeterminism grows linearly, resolving an open problem in the literature. In particular, the set of palindromes is such a language.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jonathan Goldstine, Hing Leung, Detlef Wotschke,