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
}
