Bibliography

Refining the Hierarchy of Blind Multicounter Languages and Twist-Closed Trios

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}} \}$.

BibTeX entry

@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}} \}$.}
}

Copyright Notice

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.