Matthias Jantzen and Alexy Kurganskyy.

Refining the hierarchy of Blind Multicounter languages and
Twist-Closed Trios.
*Information and Computation*, 185(2):159-181, 2003.

Abstract:We introduce the new families $(k,r)\mbox{--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 BLIND = $\mathcal{M}_{\cap}({C_1})$ of blind multicounter languages with generator $C_1=\{w\in\{a_1, b_1\}^*\mid \abs{w}_{a_1} = \abs{w}_{b_1}\}$. This thereby combines the families BLIND and RBC from [Greibach 1978] to one strict hierarchy and generalizes and sharpens Greibachs results. The strict inclusions between the $k$-counter families $(k,r)\mbox{--RBC}$ are proved using linear algebra techniques. We also study the language theoretic monadic operation $\mathit{twist}$, [Jantzen and Peterson 1987, 1994], 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)\mbox{--RBC}$ is $\mathit{twist}$-closed if and only if $r=0$, in which case $(k,0)\mbox{--RBC}=\TRIO{C_{k}}$, $C_{k}$ being the k-fold shuffle of disjoint copies of $C_{1}$. We characterize the family $\mathcal{M}_{\cap}(\mathit {PAL})$ of languages accepted in quasi-realtime by non-deterministic one-way reversal-bounded multipushdown acceptors as the least $\mathit{twist}$-closed trio $\mathcal{M}_{\mathit{twist}}(\mathit {PAL})$ generated by the set of palindromes $\mathit {PAL} =\{w \in\{a, b\}^*\mid w=w^{\mathit{rev}} \}$.

@article{Jantzen+03, Author = {Jantzen, Matthias and Kurganskyy, Alexy}, Journal = {Information and Computation}, Number = 2, Pages = {159--181}, Title = {Refining the Hierarchy of {Blind Multicounter} Languages and {Twist-Closed Trios}}, Volume = 185, Year = 2003, Abstract = {We introduce the new families $(k,r)\mbox{--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 BLIND = $\mathcal{M}_{\cap}({C_1})$ of blind multicounter languages with generator $C_1=\{w\in\{a_1, b_1\}^*\mid \abs{w}_{a_1} = \abs{w}_{b_1}\}$. This thereby combines the families BLIND and RBC from [Greibach 1978] to one strict hierarchy and generalizes and sharpens Greibachs results. The strict inclusions between the $k$-counter families $(k,r)\mbox{--RBC}$ are proved using linear algebra techniques. We also study the language theoretic monadic operation $\mathit{twist}$, [Jantzen and Peterson 1987, 1994], 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)\mbox{--RBC}$ is $\mathit{twist}$-closed if and only if $r=0$, in which case $(k,0)\mbox{--RBC}=\TRIO{C_{k}}$, $C_{k}$ being the k-fold shuffle of disjoint copies of $C_{1}$. We characterize the family $\mathcal{M}_{\cap}(\mathit {PAL})$ of languages accepted in quasi-realtime by non-deterministic one-way reversal-bounded multipushdown acceptors as the least $\mathit{twist}$-closed trio $\mathcal{M}_{\mathit{twist}}(\mathit {PAL})$ generated by the set of palindromes $\mathit {PAL} =\{w \in\{a, b\}^*\mid w=w^{\mathit{rev}} \}$.} }

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.