Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334318 | Theoretical Computer Science | 2005 | 16 Pages |
Abstract
The original model of P systems with symbol objects introduced by PÄun was shown to be computationally universal, provided that catalysts and priorities of rules are used. By reduction via register machines SosÃk and Freund proved that the priorities may be omitted from the model without loss of computational power. Freund, Oswald, and SosÃk considered several variants of P systems with catalysts (but without priorities) and investigated the number of catalysts needed for these specific variants to be computationally universal. It was shown that for the classic model of P systems with the minimal number of two membranes the number of catalysts can be reduced from six to five; using the idea of final states the number of catalysts could even be reduced to four. In this paper we are able to reduce the number of catalysts again: two catalysts are already sufficient. For extended P systems we even need only one membrane and two catalysts. For the (purely) catalytic systems considered by Ibarra only three catalysts are already enough.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Rudolf Freund, Lila Kari, Marion Oswald, Petr SosÃk,