Ponencia
P Systems with Minimal Insertion and Deletion
Autor/es | Alhazov, Artiom
Krassovitskiy, Alexander Rogozhin, Yurii Verlan, Sergey |
Fecha de publicación | 2009 |
Fecha de depósito | 2016-03-18 |
Publicado en |
|
ISBN/ISSN | 9788461328369 |
Resumen | In this paper we consider insertion-deletion P systems with priority of deletion over the insertion.We show that such systems with one symbol context-free insertion
and deletion rules are able to generate PsRE. If one-symbol ... In this paper we consider insertion-deletion P systems with priority of deletion over the insertion.We show that such systems with one symbol context-free insertion and deletion rules are able to generate PsRE. If one-symbol one-sided context is added to insertion or deletion rules but no priority is considered, then all recursively enumerable languages can be generated. The same result holds if a deletion of two symbols is permitted. We also show that the priority relation is very important and in its absence the corresponding class of P systems is strictly included in MAT. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
07_ArtiomInsDel.pdf | 219.9Kb | [PDF] | Ver/ | |