%0 Generic
%D 2005
%T Context-free insertion-deletion systems
%A Maurice Margenstern
%A Gheorghe Paun
%A Yurii Rogozhin
%A Sergey Verlan
%C Amsterdam (The Netherlands)
%I Elsevier
%K formal grammars
%K insertion-deletion systems
%K Membrane computing
%N 2
%P 339 - 348
%R 10.1016/j.tcs.2004.06.031
%U http://portal.acm.org/citation.cfm?id=1065074
%V 330
%X We consider a class of insertion-deletion systems which have not been investigated so far, those without any context controlling the insertion-deletion operations. Rather unexpectedly, we found that context-free insertion-deletion systems characterize the recursively enumerable languages. Moreover, this assertion is valid for systems with only one axiom, and also using inserted and deleted strings of a small length. As direct consequences of the main result we found that set-conditional insertion-deletion systems with two axioms generate any recursively enumerable language (this solves an open problem), as well as that membrane systems with one membrane having context-free insertion-deleletion rules without conditional use of them generate all recursively enumerable languages (this improves an earlier result). Some open problems are also formulated.