Refining the hierarchy of blind multicounter languages and twist-closed trios. (Q1427852): Difference between revisions

We introduce the new families \((k,r)\)-RBC of languages accepted in quasi-realtime by one-way counter automata having \(k\) blind counters, of which at least \(r\) are reversal-bounded. It is proved that these families form a strict and linear hierarchy of semi-AFLs within the the family \(\text{BLIND}={\mathcal M}_\cap(C_1)\) of blind multicounter languages with generator \(C_1= \{w\in \{a_1,b_1\}^*\mid |w|_{a_1}= |w|_{b_1}\}\). This thereby combines the families BLIND and RBC of \textit{S. Greibach} [Theor. Comput. Sci. 7, 311--324 (1978; Zbl 0389.68030)] to one strict hierarchy and generalizes and sharpens Greibach's results. The strict inclusions between the \(k\)-counter families \((k,r)\)-RBC are proved using linear algebra techniques. We also study the language theoretic monadic operation `twist' [see \textit{M. Jantzen} and \textit{H. Petersen}, in: K. Voss et al. (eds.), Concurrency and nets. Advances in Petri nets, 245--252 (1987; Zbl 0629.68075); Theor. Comput. Sci. 127, 149--170 (1994; Zbl 0805.68076)], in connection with the semi-AFLs of languages accepted by multicounter and multipushdown acceptors, all restricted to reversal-bounded behavior. It is verified that the family \((k,r)\)-RBC is twist-closed if and only if \(r=0\), in which case \((k,0)\text{-RBC}={\mathcal M}(C_k)\), \(C_k\) being the \(k\)-fold shuffle of disjoint copies of \(C_1\). We characterize the family \({\mathcal M}_\cap(\text{PAL})\) of languages accepted in quasi-realtime by nondeterministic one-way reversal-bounded multipushdown acceptors as the least twist-closed trio \({\mathcal M}_{\text{twist}}(\text{PAL})\) generated by the set of palindromes \(\text{PAL}= \{w\in \{a,b\}^*\mid w=w^{\text{rev}}\}\).