Lecture Notes in Computer Science, 2001, Volume 2010/2001, 376-387, DOI: 10.1007/3-540-44693-1_33

Refining the Hierarchy of Blind Multicounter Languages

Matthias Jantzen and Alexy Kurganskyy

View Related Documents

Abstract

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∩(C1) of blind multicounter languages with generator C1:={w ∈ {a1,b1*}∣ ∣wai= ∣ wbi} and RBC=M∩(B1) of reversal-bounded multicounter languages with generator B1:={an 1bn 1∣n ∈ ℕ. This generalizes and sharpens the known results from [Grei 78] and [Jant 98].

Fulltext Preview

Image of the first page of the fulltext document