RO EN
Recent Developments on Insertion-Deletion Systems
Authors: Verlan Serghei
Keywords: insertion-deletion systems, computational completeness, decidability, graph control, P systems.
– 0.28 Mb
Keywords: insertion-deletion systems, computational completeness, decidability, graph control, P systems.
Abstract
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
E-mail:
Institute of Mathematics and Computer Science,
Academy of Sciences of Moldova
Academiei 5, Chișinău MD 2028 Moldova
61, av gen. de Gaulle
94010 Creteil, France
Phone: +33145176600
E-mail:
Institute of Mathematics and Computer Science,
Academy of Sciences of Moldova
Academiei 5, Chișinău MD 2028 Moldova
Fulltext
– 0.28 Mb
Contents
- Gheorghe Pãun (A tribute in honour of his 60th birthday)
- Investigations on Natural Computing in the Institute of Mathematics and Computer Science
- Membrane Systems Languages Are Polynomial-Time Parsable
- Minimal Parallelism and Number of Membrane Polarizations
- On computational properties of gene assembly in ciliates
- Recent Developments on Insertion-Deletion Systems
- Simulator of P-Systems with String Replication Developed in Framework of P-Lingua 2.1
