Restrictions on Multicounter and Partially-Blind Multicounter Languages
Óscar H. Ibarra, Ian McQuillan · Computer Science Journal of Moldova · 2024
We introduce a new way of defining languages accepted by multicounter machines. Given a multicounter machine M and m ≥ 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 reversalbounded 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.