It cannot be decided whether a one-counter automaton accepts each string in its language using a counter whose value is bounded by a constant. Furthermore, when the counter is bounded by a constant, its value cannot be limited by any recursive function in the size of the machine. We consider three measures: the costs of all computations (strong measure), all accepting computations (accept measure), and the least expensive accepting computation (weak measure). By taking into account the strong and accept measures, the above-mentioned problem becomes decidable for both pushdown automata and one-counter automata. Moreover, the bounds for the pushdown height or the value of the counter, when non constant, are recursive in the size of the machine. We also prove that, under the weak measure, if a one-counter automaton accepts with a counter that, with respect to the input length is not bounded by any constant, then the counter grows at least as a logarithmic function. This bound can be reached. This is in contrast with the case of pushdown automata in which the optimal bound is double logarithmic. For the strong and accept measures these bounds are shown to be linear, for both pushdown and one-counter automata.
Pushdown and One-Counter Automata: Constant and Non-constant Memory Usage / G. Pighizzini, L. Prigioniero (LECTURE NOTES IN COMPUTER SCIENCE). - In: Descriptional Complexity of Formal Systems / [a cura di] H. Bordihn, N. Tran, G. Vaszil. - [s.l] : Springer Science and Business Media Deutschland GmbH, 2023. - ISBN 978-3-031-34325-4. - pp. 146-157 (( Intervento presentato al 25. convegno International Conference on Descriptional Complexity of Format Systems tenutosi a Potsdam nel 2023 [10.1007/978-3-031-34326-1_11].
Pushdown and One-Counter Automata: Constant and Non-constant Memory Usage
G. Pighizzini;L. Prigioniero
2023
Abstract
It cannot be decided whether a one-counter automaton accepts each string in its language using a counter whose value is bounded by a constant. Furthermore, when the counter is bounded by a constant, its value cannot be limited by any recursive function in the size of the machine. We consider three measures: the costs of all computations (strong measure), all accepting computations (accept measure), and the least expensive accepting computation (weak measure). By taking into account the strong and accept measures, the above-mentioned problem becomes decidable for both pushdown automata and one-counter automata. Moreover, the bounds for the pushdown height or the value of the counter, when non constant, are recursive in the size of the machine. We also prove that, under the weak measure, if a one-counter automaton accepts with a counter that, with respect to the input length is not bounded by any constant, then the counter grows at least as a logarithmic function. This bound can be reached. This is in contrast with the case of pushdown automata in which the optimal bound is double logarithmic. For the strong and accept measures these bounds are shown to be linear, for both pushdown and one-counter automata.File | Dimensione | Formato | |
---|---|---|---|
OneCounter.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
428.43 kB
Formato
Adobe PDF
|
428.43 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
978-3-031-34326-1_11.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
286.7 kB
Formato
Adobe PDF
|
286.7 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.