2023/01/24 by Pascal Baumann, Baumann, Pascal, Flavio D’Alessandro +11
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2301.10198
openalex publication_date 2023/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 coNP-complete to decide whether a given (P)RBCA language L is bounded, meaning whether there exist words w1,…,wn with L⊆ w1^*⋯ wn^*. 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 ℤ-counters in logarithmic space, while preserving the accepted language.