Refining the hierarchy of blind multicounter languages and twist-closed trios

AbstractWe introduce the new families (k,r)-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=M∩(C−1) of blind multicounter languages with generator C−1={w∈{a−1,b−1}*∣w−a−1=w−b−1}. This thereby combines the families BLIND and RBC from [13] to one strict hierarchy and generalizes and sharpens Greibachs results.The strict inclusions between the k-counter families (k,r)-RBC are proved using linear algebra techniques.We also study the language theoretic monadic operation twist [18,20], 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)-RBC is twist-closed if and only if r=0, in which case (k,0)-RBC=M(C−k), C−k being the k-fold shuffle of disjoint copies of C−1.We characterize the family M∩(PAL) of languages accepted in quasi-realtime by non-deterministic one-way reversal-bounded multipushdown acceptors as the least twist-closed trio Mtwist(PAL) generated by the set of palindromes PAL={w∈{a,b}*∣w=wrev}