Context-free insertion-deletion systems

TitleContext-free insertion-deletion systems
Publication TypeJournal Papers
Year of Publication2005
AuthorsMargenstern, M., Paun G., Rogozhin Y., & Verlan S.
Journal TitleTheoretical Computer Science
Place PublishedAmsterdam (The Netherlands)
Pages339 - 348

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.

Keywordsformal grammars, insertion-deletion systems, Membrane computing
ISSN Number0304-3975