We show that the families (k, r)-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 BLIND = M_∩(C_1) of blind multicounter languages with generator C_1 := {w ∈ {a_1, b_1}~* | |w|_(a_1) = |w|_(b_1)} and RBC = M_∩(B_1) of reversal-bounded multicounter languages with generator B_1= {a_1~nb_1~n | n ∈ N}. This generalizes and sharpens the known results from [Grei 78] and [Jant 98].
展开▼
机译：我们表明，具有k个盲计数器的单向计数器自动机（准实时）接受（准实时）的语言的族（k，r）-RBC构成了半AFL的严格且线性的层次结构。此层次结构包含具有生成器C_1的盲多计数器语言的BLIND =M_∩（C_1）族：= {w∈{a_1，b_1}〜* | | w | _（a_1）= | w | _（b_1）}，并且RBC =M_∩（B_1）的反向边界多计数器语言，生成器B_1 = {a_1〜nb_1〜n | n∈N}。这概括并锐化了[Grei 78]和[Jant 98]的已知结果。
展开▼
