Push Complexity: Optimal Bounds and Unary Inputs

The notion of push complexity has been recently introduced by Bordhin and Mitrana 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. This lower bound is optimal. Indeed, we prove that there exists a language with push complexity  \(O(\log \log n)\) . 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.