| Autor: |
Baumann, Pascal, D'Alessandro, Flavio, Ganardi, Moses, Ibarra, Oscar, McQuillan, Ian, Schütze, Lia, Zetzsche, Georg |
| Rok vydání: |
2023 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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 $w_1,\ldots,w_n$ with $L\subseteq w_1^*\cdots 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}$-counters in logarithmic space, while preserving the accepted language. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
