How to Obtain Computational Completeness in P Systems with One Catalyst

Rudolf Freund
(TU Wien)
Gheorghe Păun

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.

In Turlough Neary and Matthew Cook: Proceedings Machines, Computations and Universality 2013 (MCU 2013), Zürich, Switzerland, 9/09/2013 - 11/09/2013, Electronic Proceedings in Theoretical Computer Science 128, pp. 47–61.
Published: 4th September 2013.

ArXived at: http://dx.doi.org/10.4204/EPTCS.128.13 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org