Morphic characterizations of languages in Chomsky hierarchy with insertion and locality

This paper concerns new characterizations of regular, context-free, and recursively enumerable languages, using insertion systems with lower complexity. This is achieved by using both strictly locally testable languages and morphisms. The representation is in a similar way to the Chomsky-Schu¨tzenberger representation of context-free languages. Specifically, each recursively enumerable language L can be represented in the form L=h(L(γ)∩R), where γ is an insertion system of weight (3,3), R is a strictly 2-testable language, and h is a projection. A similar representation can be obtained for context-free languages, using insertion systems of weight (2,0) and strictly 2-testable languages, as well as for regular languages, using insertion systems of weight (1,0) and strictly 2-testable languages.