Back to Search
Start Over
P systems with minimal insertion and deletion
- Source :
-
Theoretical Computer Science . Jan2011, Vol. 412 Issue 1/2, p136-144. 9p. - Publication Year :
- 2011
-
Abstract
- Abstract: In this paper, we consider insertion–deletion P systems with priority of deletion over insertion. We show that such systems with one-symbol context-free insertion and deletion rules are able to generate Parikh sets of all recursively enumerable languages (). If a one-symbol one-sided context is added to the insertion or deletion rules, 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 the family of matrix languages (). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 412
- Issue :
- 1/2
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 55502467
- Full Text :
- https://doi.org/10.1016/j.tcs.2010.08.025