アイテム詳細

要旨

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.