On the Computational Power of 1-Deterministic and Sequential P Systems

• Autorzy: Ibarra O.H. , Woodworth S. , Yen H-C. , Dang Z.
• Języki publikacji: EN

Abstrakty

EN

The original definition of P systems calls for rules to be applied in a maximally parallel fashion. However, in some cases a sequential model may be a more reasonable assumption. Here we study the computational power of different variants of sequential P systems. Initially we look at cooperative systems operating on symbol objects and without prioritized rules, but which allow membrane dissolution and bounded creation rules. We show that they are equivalent to vector addition systems and, hence, nonuniversal. When these systems are used as language acceptors, they are equivalent to communicating P systems which, in turn, are equivalent to partially blind multicounter machines. In contrast, if such cooperative systems are allowed to create an unbounded number of new membranes (i.e., with unbounded membrane creation rules) during the course of the computation, then they become universal. We then consider systems with prioritized rules operating on symbol objects. We show two types of results: there are sequential P systems that are universal and sequential P systems that are nonuniversal. In particular, both communicating and cooperative P systems are universal, even if restricted to 1-deterministic systems with one membrane. However, the reachability problem for multi-membrane catalytic P systems with prioritized rules is NP-complete and, hence, these systems are nonuniversal.

Słowa kluczowe

EN

sequential P system; 1-deterministic P system; communicating P system; catalytic system; vector addition system; partially blind counter machine

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 133--152
• Opis fizyczny: bibliogr. 20 poz.

Twórcy

autor

Ibarra O.H.

autor

Woodworth S.

autor

Yen H-C.

autor

Dang Z.

• Department of Computer Science, University of California Santa Barbara, CA 93106, USA,

Bibliografia

• [1] E. Csuhaj-Varju, O.H. Ibarra, G. Vaszil: On the computational complexity of P automata. Proc DNA10, Milano, 2004 (C. Ferretti, G. Mauri, C. Zandron, eds.), LNCS 3384, Springer, Berlin, 2005, 76-89.
• [2] Z. Dang, O.H. Ibarra: On P systems operating in sequential and limited parallel modes. Pre-Proceedings of 6th Workshop on Descriptional Complexity of Formal Systems, London, Ontario, 2004, 164-177.
• [3] R. Freund, Gh. Pǎun: On deterministic P systems, See P Systems Web Page at http://www.psystems.disco.unimib.it/ 2003.
• [4] L. Fribourg, H. Olsen: Proving safety properties of infinite state systems by compilation into Presburger Arithmetic. CONCUR'97, LNCS 1243, Springer, Berlin, 1997, 213-227.
• [5] P. Frisco: About P systems with symport/antiport. Second Brainstorming Week on Membrane Computing, Sevilla, Spain, 2004, 224-236.
• [6] S.A. Greibach: Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science, 7, 3 (1978), 311-324.
• [7] J. Hopcroft, J.-J. Pansiot: On the reachability problemfor 5-dimensional vector addition systems. Theoretical Computer Science, 8, 2 (1979), 135-159.
• [8] O.H. Ibarra: On the computational complexity of membrane systems. Theoretical Computer Science, 320, 1 (2004), 89-109.
• [9] O.H. Ibarra, Z. Dang, O. Egecioglu: Catalytic P systems, semilinear sets, and vector addition systems. Theoretical Computer Science, 11, 1 (2004), 167-181.
• [10] O.H. Ibarra, H. Yen, Z. Dang: On the power of maximal parallelism in P systems. Developments in Language Theory 2004, LNCS 3340, Springer, Berlin, 2004, 212-224.
• [11] C. Martin-Vide, A. P˘aun, Gh. P˘aun: On the power of P systems with symport rules. Journal of Universal Computer Science, 8, 2 (2002), 317-331.
• [12] E. Mayr: An algorithm for the general Petri net reachability problem. SIAM J. Computing, 13 (1984), 441-460.
• [13] M. Minsky: Recursive unsolvability of Post's problem of Tag and other topics in the theory of Turing machines. Ann. of Math., 74 (1961), 437-455.
• [14] M. Mutyam, K. Kriithivasan: P systems with active objects: Universality and efficiency. Proceedings of the Third International Conference on Machines, Computations, and Universality, Chis¸in˘au, Moldova, May 23-27 2001, 276 - 287.
• [15] A. Pǎun, Gh. Pǎun: The power of communication: P systems with symport/antiport. New Generation Computing, 20, 3 (2002), 295-306.
• [16] Gh. Pǎun: Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108-143.
• [17] Gh. Pǎun: Membrane Computing: An Introduction. Springer, Berlin, 2002.
• [18] P. Sosik: P systems versus register machines: two universality proofs. Pre-Proceedings of Workshop onMembrane Computing (WMC-CdeA2002), Curtea de Arges¸, Romania, 2002.
• [19] H. Yen: On reachability equivalence for BPP-nets, Theoretical Computer Science, 179 (1997), 301-317.
• [20] H. Yen: Priority conflict-free Petri nets. Acta Informatica, 35, 8 (1998), 673-688.