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.

Pushdown automata and constant height: decidability and bounds / G. Pighizzini, L. Prigioniero. - In: ACTA INFORMATICA. - ISSN 0001-5903. - (2022 Jul 27), pp. 1-22. [10.1007/s00236-022-00434-0]

Pushdown automata and constant height: decidability and bounds

G. Pighizzini;L. Prigioniero
2022

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.
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
File Dimensione Formato  
s00236-022-00434-0.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 463.67 kB
Formato Adobe PDF
463.67 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/939758
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
social impact