We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Pushdown automata and constant height: decidability and bounds.
- Authors
Pighizzini, Giovanni; Prigioniero, Luca
- Abstract
It cannot be decided whether a pushdown automaton accepts using a pushdown height, which does not depend on the input length, i.e., when it accepts using constant height. Furthermore, when a pushdown automaton accepts in constant height, the height can be arbitrarily large with respect to the size of the description of the machine, namely it does not exist any recursive function in the size of the description of the machine bounding the height of the pushdown. In contrast, in the restricted case of pushdown automata over a one-letter input alphabet, i.e., unary pushdown automata, the situation is different. First, acceptance in constant height is decidable. Moreover, in the case of acceptance in constant height, the height is at most exponential with respect to the size of the description of the pushdown automaton. We also prove a matching lower bound. Finally, if a unary pushdown automaton uses nonconstant height to accept, then the height should grow at least as the logarithm of the input length. This bound is optimal.
- Subjects
RECURSIVE functions; LOGARITHMS
- Publication
Acta Informatica, 2023, Vol 60, Issue 2, p123
- ISSN
0001-5903
- Publication type
Article
- DOI
10.1007/s00236-022-00434-0