How to Obtain Computational Completeness in P Systems with One Catalyst
Whether P systems with only one catalyst can already be computationally complete, is still an open problem. Here we establish computational completeness by using specific variants of additional control mechanisms. At each step using only multiset rewriting rules from one set of a finite number of se...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2013-09-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1309.1267v1 |
| _version_ | 1811278854010961920 |
|---|---|
| author | Rudolf Freund Gheorghe Păun |
| author_facet | Rudolf Freund Gheorghe Păun |
| author_sort | Rudolf Freund |
| collection | DOAJ |
| description | Whether P systems with only one catalyst can already be computationally complete, is still an open problem. Here we establish computational completeness by using specific variants of additional control mechanisms. At each step using only multiset rewriting rules from one set of a finite number of sets of multiset rewriting rules allows for obtaining computational completeness with one catalyst and only one membrane. If the targets are used for choosing the multiset of rules to be applied, for getting computational completeness with only one catalyst more than one membrane is needed. If the available sets of rules change periodically with time, computational completeness can be obtained with one catalyst in one membrane. Moreover, we also improve existing computational completeness results for P systems with mobile catalysts and for P systems with membrane creation. |
| first_indexed | 2024-04-13T00:44:02Z |
| format | Article |
| id | doaj.art-256c5cfd33674ff4adab049ce48b9528 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-04-13T00:44:02Z |
| publishDate | 2013-09-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-256c5cfd33674ff4adab049ce48b95282022-12-22T03:10:04ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802013-09-01128Proc. MCU 2013476110.4204/EPTCS.128.13How to Obtain Computational Completeness in P Systems with One CatalystRudolf FreundGheorghe PăunWhether P systems with only one catalyst can already be computationally complete, is still an open problem. Here we establish computational completeness by using specific variants of additional control mechanisms. At each step using only multiset rewriting rules from one set of a finite number of sets of multiset rewriting rules allows for obtaining computational completeness with one catalyst and only one membrane. If the targets are used for choosing the multiset of rules to be applied, for getting computational completeness with only one catalyst more than one membrane is needed. If the available sets of rules change periodically with time, computational completeness can be obtained with one catalyst in one membrane. Moreover, we also improve existing computational completeness results for P systems with mobile catalysts and for P systems with membrane creation.http://arxiv.org/pdf/1309.1267v1 |
| spellingShingle | Rudolf Freund Gheorghe Păun How to Obtain Computational Completeness in P Systems with One Catalyst Electronic Proceedings in Theoretical Computer Science |
| title | How to Obtain Computational Completeness in P Systems with One Catalyst |
| title_full | How to Obtain Computational Completeness in P Systems with One Catalyst |
| title_fullStr | How to Obtain Computational Completeness in P Systems with One Catalyst |
| title_full_unstemmed | How to Obtain Computational Completeness in P Systems with One Catalyst |
| title_short | How to Obtain Computational Completeness in P Systems with One Catalyst |
| title_sort | how to obtain computational completeness in p systems with one catalyst |
| url | http://arxiv.org/pdf/1309.1267v1 |
| work_keys_str_mv | AT rudolffreund howtoobtaincomputationalcompletenessinpsystemswithonecatalyst AT gheorghepaun howtoobtaincomputationalcompletenessinpsystemswithonecatalyst |