Unboundedness Problems for Machines with Reversal-Bounded Counters
Pascal Baumann, Flavio D’Alessandro, Moses Ganardi, Óscar H. Ibarra, Ian McQuillan, Lia Schütze, Georg Zetzsche · Lecture notes in computer science · 2023
Abstract We consider a general class of decision problems concerning formal languages, called “(one-dimensional) unboundedness predicates”, for automata that feature reversal-bounded counters (RBCA). We show that each problem in this class reduces—non-deterministically in polynomial time—to the same problem for just finite automata. We also show an analogous reduction for automata that have access to both a pushdown stack and reversal-bounded counters (PRBCA). This allows us to answer several open questions: For example, we show that it is $$\textsf{coNP}$$ coNP -complete to decide whether a given (P)RBCA language L is bounded, meaning whether there exist words $$w_1,\ldots ,w_n$$ w 1 , … , w n with $$L\subseteq w_1^*\cdots w_n^*$$ L ⊆ w 1 ∗ ⋯ w n ∗ . For PRBCA, even decidability was open. Our methods also show that there is no language of a (P)RBCA of intermediate growth. This means, the number of words of each length grows either polynomially or exponentially. Part of our proof is likely of independent interest: We show that one can translate an RBCA into a machine with $$\mathbb {Z}$$ Z -counters in logarithmic space, while preserving the accepted language.