Restrictions on Multicounter and Partially-Blind Multicounter Languages

Abstract

We introduce a new way of defining languages accepted by multicounter machines. Given a multicounter machine $M$ and $m \ge 0$, the $m$-crossing language accepted by $M$ is the set of all words where there is an accepting computation of $M$ on $w$ such that, for each counter $j$, each value $c$ that can appear in the counter is crossed at most $m$ times. We study this concept with multicounter machines and also with the partially-blind restriction where a counter cannot detect whether it contains zero or not. We show that both multicounter and partially-blind multicounter languages with one cross define exactly the reversal-bounded multicounter languages, while two crosses can accept strictly more including non-semilinear languages. We find that surprisingly, the family of $m$-crossing languages accepted by multicounter machines, for some $m$, and the family of $m$-crossing languages accepted by partially-blind multicounter machines, for some $m$, coincide. Decidability properties regarding $m$-crossing languages are also analyzed.