THE LINEAR LANDSCAPE OF EXTERNAL CONTEXTUAL LANGUAGES

The class of external contextual languages is strictly included in the class of linear languages. A reason for the strict inclusion in linea r languages is that external contextual grammars generate languages in the exhaustive way: each sentential form belongs to the language of a grammar. In this paper we study the effect of adding various squeezin g mechanisms to the basic classes of exhaustive contextual grammars. W e obtain in this way a characterization of linear languages and a whol e landscape of sublinear families. By restricting the contexts to be o ne-sided (only left-sided or only right-sided) we obtain a characteriz ation of regular languages - here the subregular landscape reduces to two families.