They all generate the class of mildly context-sensitive languages (MCSL), all members of which have recognition algorithms with time complexity O(n 6 ) (Vijay-Shanker and Weir, 1993;Satta, 1994).
1 of the weak equivalence of four independently developed (and linguistically motivated) extensions of CFG, the class MCSL is considered to be linguistically meaningful, a natural class of languages for characterizing natural languages.