Bibliographie

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.

Kurzfassung: 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-Eintrag

@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-Hinweis

Diese Informationen werden zur Verfügung gestellt, um technische und Forschungsarbeiten zeitnah bekannt zu geben. Das Urheberrecht und alle damit verbundenen Rechte verbleiben bei den Autoren bzw. anderen Rechteinhabern. Von jedem, der Informationen dieser Seiten übernimmt, wird erwartet, dass er sich an die jeweiligen Bedingungen und Beschränkungen der Rechteinhaber hält. Meist bedeutet dies, dass die hier bereitgestellten Daten nicht ohne explizite Genehmigung der Rechteinhaber weiterveröffentlicht werden dürfen.