Bibliography

Refining the Hierarchy of Blind Multicounter Languages

Matthias Jantzen and Alexy Kurganskyy.
Refining the hierarchy of blind multicounter languages.
Bericht des Fachbereichs Informatik FBI-HH-B- 229/01, Universität Hamburg, Fachbereich Informatik, Vogt-Kölln Str. 30, D-22527 Hamburg, 2001.

BibTeX

@techreport{Jantzen+01,
 Abstract = {We show that the families
$(k,r)\mbox{--$\mathit{RBC}$}$ of languages accepted (in quasi-realtime)
by one-way counter automata having $k$~blind counters of which $r$ are
reversal-bounded form a strict and linear hierarchy of semi-AFLs. This
hierarchy comprises the families $\mathit{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}\}$ and
$RBC = \mathcal{M}_{\cap}({B_1})$ of  reversal-bounded multicounter languages
with generator $B_1 := \{a_1^n b_1^n \mid n\in \N \}$. This generalizes and sharpens the known
results from [Greibach 1978] and [Jantzen 1998]. The proof for the strict inclusions for
the  first time uses techniques from linear algebra.},
 Address = FBIUniAdresse,
 Author = {Jantzen, Matthias and Kurganskyy, Alexy},
 Institution = FBIUniHHbis2005,
 Number = {FBI-HH-B- 229/01},
 Pages = 18,
 Type = FBIBericht,
 Title = {Refining the Hierarchy of Blind Multicounter Languages},
 Year = 2001
}