@article {,
	title = {Context-free insertion-deletion systems},
	journal = {Theoretical Computer Science},
	volume = {330},
	year = {2005},
	pages = {339 - 348},
	publisher = {Elsevier},
	address = {Amsterdam (The Netherlands)},
	abstract = {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. 


},
	keywords = {formal grammars, insertion-deletion systems, Membrane computing},
	issn = {0304-3975 },
	doi = {10.1016/j.tcs.2004.06.031 },
	url = {http://portal.acm.org/citation.cfm?id=1065074},
	author = {Maurice Margenstern and Gheorghe Paun and Yurii Rogozhin and Sergey Verlan}
}
