CHARACTERIZATIONS OF RECURSIVELY-ENUMERABLE LANGUAGES BY MEANS OF INSERTION GRAMMARS

An insertion grammar is based on pure rules of the form uv --> uxv (th e string x is inserted in the context (u, v)). A strict subfamily of t he context-sensitive family is obtained, incomparable with the family of linear languages. We prove here that each recursively enumerable la nguage can be written as the weak coding of the image by an inverse mo rphism of a language generated by an insertion grammar (with the maxim al length of strings u, v as above equal to seven). This result is rat her surprising in view of some closure properties established earlier in the literature. Some consequences of this result are also stated. W hen also erasing rules of the form uxv --> uv are present (the string x is erased from the context (u,v)), then a much easier representation of recursively enumerable languages is obtained, as the intersection with V of a language generated by an insertion grammar with erased st rings (having the maximal length of strings u, v as above equal to two ). (C) 1998-Elsevier Science B.V. All rights reserved.