Computational Power of P Systems with Small Size Insertion and Deletion Rules
Recent investigations show insertion-deletion systems of small size that are not complete and cannot generate all recursively enumerable languages. However, if additional computational distribution mechanisms like P systems are added, then the computational completeness is achieved in some cases. In...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2009-06-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/0906.3119v1 |
| _version_ | 1811277130257924096 |
|---|---|
| author | Sergey Verlan Yurii Rogozhin Alexander Krassovitskiy |
| author_facet | Sergey Verlan Yurii Rogozhin Alexander Krassovitskiy |
| author_sort | Sergey Verlan |
| collection | DOAJ |
| description | Recent investigations show insertion-deletion systems of small size that are not complete and cannot generate all recursively enumerable languages. However, if additional computational distribution mechanisms like P systems are added, then the computational completeness is achieved in some cases. In this article we take two insertion-deletion systems that are not computationally complete, consider them in the framework of P systems and show that the computational power is strictly increased by proving that any recursively enumerable language can be generated. At the end some open problems are presented. |
| first_indexed | 2024-04-13T00:10:11Z |
| format | Article |
| id | doaj.art-561e0e0ff7f44d5185c978cd6e023d3e |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-04-13T00:10:11Z |
| publishDate | 2009-06-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-561e0e0ff7f44d5185c978cd6e023d3e2022-12-22T03:11:07ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802009-06-011Proc. CSP 200810811710.4204/EPTCS.1.10Computational Power of P Systems with Small Size Insertion and Deletion RulesSergey VerlanYurii RogozhinAlexander KrassovitskiyRecent investigations show insertion-deletion systems of small size that are not complete and cannot generate all recursively enumerable languages. However, if additional computational distribution mechanisms like P systems are added, then the computational completeness is achieved in some cases. In this article we take two insertion-deletion systems that are not computationally complete, consider them in the framework of P systems and show that the computational power is strictly increased by proving that any recursively enumerable language can be generated. At the end some open problems are presented.http://arxiv.org/pdf/0906.3119v1 |
| spellingShingle | Sergey Verlan Yurii Rogozhin Alexander Krassovitskiy Computational Power of P Systems with Small Size Insertion and Deletion Rules Electronic Proceedings in Theoretical Computer Science |
| title | Computational Power of P Systems with Small Size Insertion and Deletion Rules |
| title_full | Computational Power of P Systems with Small Size Insertion and Deletion Rules |
| title_fullStr | Computational Power of P Systems with Small Size Insertion and Deletion Rules |
| title_full_unstemmed | Computational Power of P Systems with Small Size Insertion and Deletion Rules |
| title_short | Computational Power of P Systems with Small Size Insertion and Deletion Rules |
| title_sort | computational power of p systems with small size insertion and deletion rules |
| url | http://arxiv.org/pdf/0906.3119v1 |
| work_keys_str_mv | AT sergeyverlan computationalpowerofpsystemswithsmallsizeinsertionanddeletionrules AT yuriirogozhin computationalpowerofpsystemswithsmallsizeinsertionanddeletionrules AT alexanderkrassovitskiy computationalpowerofpsystemswithsmallsizeinsertionanddeletionrules |