RO  EN
IMI/Publicaţii/CSJM/Ediţii/CSJM v.32, n.3 (96), 2024/

Restrictions on Multicounter and Partially-Blind Multicounter Languages

Authors: Oscar H. Ibarra, Ian McQuillan

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.\footnote[1]{\ \ Supported, in part, by Natural Sciences and Engineering Research Council of Canada Grant 2022-05092 (Ian McQuillan)

Oscar Ibarra
Department of Computer Science, University of California,
Santa Barbara, CA 93106, USA
E-mail:

Ian McQuillan
Department of Computer Science, University of Saskatchewan
Saskatoon, SK S7N 5A9, Canada
E-mail:

DOI

https://doi.org/10.56415/csjm.v32.20

Fulltext

Adobe PDF document – 0.32 Mb