<?xml version="1.0" encoding="UTF-8"?><xml><records><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Maurice Margenstern</style></author><author><style face="normal" font="default" size="100%">Gheorghe Paun</style></author><author><style face="normal" font="default" size="100%">Yurii Rogozhin</style></author><author><style face="normal" font="default" size="100%">Sergey Verlan</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Context-free insertion-deletion systems</style></title><secondary-title><style face="normal" font="default" size="100%">Theoretical Computer Science</style></secondary-title></titles><keywords><keyword><style  face="normal" font="default" size="100%">formal grammars</style></keyword><keyword><style  face="normal" font="default" size="100%">insertion-deletion systems</style></keyword><keyword><style  face="normal" font="default" size="100%">Membrane computing</style></keyword></keywords><dates><year><style  face="normal" font="default" size="100%">2005</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://portal.acm.org/citation.cfm?id=1065074</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">Elsevier</style></publisher><pub-location><style face="normal" font="default" size="100%">Amsterdam (The Netherlands)</style></pub-location><volume><style face="normal" font="default" size="100%">330</style></volume><pages><style face="normal" font="default" size="100%">339 - 348</style></pages><abstract><style face="normal" font="default" size="100%">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. 


</style></abstract><issue><style face="normal" font="default" size="100%">2</style></issue></record></records></xml>