IMI/Publicaţii/CSJM/Ediţii/CSJM v.18, n.2 (53), 2010/

Recent Developments on Insertion-Deletion Systems

Authors: Verlan Serghei
Keywords: insertion-deletion systems, computational completeness, decidability, graph control, P systems.


This article gives an overview of the recent developments in the study of the operations of insertion and deletion. It presents the origin of these operations, their formal definition and a series of results concerning language properties, decidability and computational completeness of families of languages generated by insertion-deletion systems and their extensions with the graph-control. The basic proof methods are presented and the proofs for the most important results are sketched.

LACL, University of Paris Est,
61, av gen. de Gaulle
94010 Creteil, France
Phone: +33145176600

Institute of Mathematics and Computer Science,
Academy of Sciences of Moldova
Academiei 5, Chișinău MD 2028 Moldova


Adobe PDF document0.28 Mb