Unboundedness problems for machines with reversal-bounded counters

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 coNP-complete to decide whether a given (P)RBCA language $L$ is bounded, meaning whether there exist words $w_{1}, l d o t s, w_{n}$ with $L s u b s e t e q w_{1}^{*} c d o t s 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 $m a t h b b Z$ -counters in logarithmic space, while preserving the accepted language.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Unboundedness problems for machines with reversal-bounded counters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6091196)