Skip to Main content Skip to Navigation
Conference papers

Pushdown Automata and Constant Height: Decidability and Bounds

Abstract : It cannot be decided whether a pushdown automaton accepts using constant pushdown height, with respect to the input length, or not. Furthermore, in the case of acceptance in constant height, the height cannot be bounded by any recursive function in the size of the description of the machine. In contrast, in the restricted case of pushdown automata over a one-letter input alphabet, i.e., unary pushdown automata, the above property becomes decidable. Moreover, if the height is bounded by a constant in the input length, then it is at most exponential with respect to the size of the description of the pushdown automaton. This bound cannot be reduced. 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-02387302
Contributor : Hal Ifip <>
Submitted on : Friday, November 29, 2019 - 4:36:25 PM
Last modification on : Friday, November 29, 2019 - 5:01:48 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Giovanni Pighizzini, Luca Prigioniero. Pushdown Automata and Constant Height: Decidability and Bounds. 21th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.260-271, ⟨10.1007/978-3-030-23247-4_20⟩. ⟨hal-02387302⟩

Share

Metrics

Record views

62