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.

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

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