Simple matrix languages

Simple matrix languages and right-linear simple matrix languages are defined as subfamilies of matrix languages by putting restrictions on the form and length (degree) of the rewriting rules associated with matrix grammars. For each n ⩾ 1, let L(n)[ℛ(n)] be the class of simple matrix languages [right-linear simple matrix languages] of degree n, and letL=⋃n⩾1L(n)[ℛ=⋃n⩾1ℛ(n)].It is shown that L(1)[ℛ(1)] coincides with the class of context-free languages [regular sets] and that L is a proper subset of the family of languages accepted by deterministic linear bounded automata. It is proved that L(n)[ℛ(n)] forms a hierarchy of classes of languages in L[ℛ]. The closure properties and decision problems associated with L(n), L, ℛ(n), and ℛ are thoroughly investigated.Let LB[ℛB] be the bounded languages in L[ℛ]. It is shown that LB=ℛB and that most of the positive closure and decision results which are true for bounded context-free languages are carried over in LB. A characterization of LB as the smallest family of languages which contains the bounded context-free languages and which is closed under the operations of union and intersection is proved