Push complexity: Optimal bounds and decidability

The notion of push complexity has been introduced by Bordhin and Mitrana in 2020 as a measure of nonregularity for context-free languages. This measure takes into account the number of push operations used to accept inputs of length n. We show that the push complexity of each nonregular context-free language grows at least as a double logarithmic function, with respect to the length of the strings. Furthermore, we prove that there exists a language matching this lower bound which, hence, is optimal. It is known that it cannot be decided whether the number of push operations used by a pushdown automaton is bounded by any constant. We prove that, in the restricted case of pushdown automata with a one-letter input alphabet, this question is decidable. Furthermore, under the same restriction, if the number of push operations used by a pushdown automaton is not bounded by any constant, then it should grow at least as a linear function in the length of the input.