C. Martinvide et al., CHARACTERIZATIONS OF RECURSIVELY-ENUMERABLE LANGUAGES BY MEANS OF INSERTION GRAMMARS, Theoretical computer science, 205(1-2), 1998, pp. 195-205
Citations number
15
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Theory & Methods
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.