Abstract
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.
The work of Oscar H. Ibarra was supported in part by NSF Grants CCR-0208595 and CCF-0430945. The research of Hsu-Chun Yen was supported in part by NSC Grant 93-2213-E-002-003, Taiwan. The work of Zhe Dang was supported in part by NSF Grant CCF-0430531
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Csuhaj-Varju, E., Ibarra, O., Vaszil, G.: On the computational complexity of P automata. In: Proc. DNA 10 (2004)
Dang, Z., Ibarra, O.: On P systems operating in sequential mode. Pre-Proc. DCFS 2004 (2004)
Freund, R.: Sequential P-systems (2000), Available at http://psystems.disco.unimib.it
Freund, R.: Asynchronous P systems. In: Mauri, G., Paun, G., Zandron, C. (eds.) Pre-Proc. Fifth Workshop on Membrane Computing (2004)
Freund, R., Paun, G.: On deterministic P systems (2003), See P Systems Web Page at http://psystems.disco.unimib.it
Frisco, P.: About P systems with symport/antiport. In: Second Brainstorming Week on Membrane Computing, Sevilla, Spain, pp. 224–236, February 2-7 (2004)
Greibach, S.: Remarks on blind and partially blind one-way multicounter machines. Theor. Comput. Sci. 7, 311–324 (1978)
Hopcroft, J., Pansiot, J.J.: On the reachability problem for 5-dimensional vector addition systems. Theor. Comput. Sci. 8(2), 135–159 (1979)
Ibarra, O.: On the computational complexity of membrane systems. Theor. Comput. Sci. 320(1), 89–109 (2004)
Ibarra, O., Dang, Z., Egecioglu, O.: Catalytic P systems, semilinear sets, and vector addition systems. Theor. Comput. Sci. 11(1), 167–181 (2004)
Ibarra, O., Yen, H., Dang, Z.: On the power of maximal parallelism in P systems. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT 2004. LNCS, vol. 3340, pp. 212–224. Springer, Heidelberg (2004)
Martin-Vide, C., Paun, A., Paun, G.: On the power of P systems with symport rules. Journal of Universal Computer Science 8(2), 317–331 (2002)
Mayr, E.: An algorithm for the general Petri net reachability problem, SIAM J. Computing 13(3), 441–460 (1984)
Minsky, M.: Recursive unsolvability of Post’s problem of tag and other topics in the theory of Turing machines. Ann. of Math 74, 437–455 (1961)
Mutyam, M., Kriithivasan, K.: P systems with active objects: Universality and efficiency. In: Proc. of the 3rd Int’l Conf. on Machines, Computations, and Universality, May 23-27, 2001, pp. 276–287 (2001)
Paun, A., Paun, G.: The power of communication: P systems with symport/antiport, New. Generation Computing 20(3), 295–306 (2002)
Paun, G.: Computing with membranes. Journal of Computer and System Sciences 61(1), 108–143 (2000)
Paun, G.: Membrane Computing: An Introduction. Springer, Heidelberg (2002)
Sosik, P.: P systems versus register machines: Two universality proofs. In: Păun, G., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) WMC 2002. LNCS, vol. 2597, pp. 371–382. Springer, Heidelberg (2003)
Yen, H.: Priority conflict-free Petri nets. Acta Informatica 35(8), 673–688 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ibarra, O.H., Woodworth, S., Yen, HC., Dang, Z. (2005). On Sequential and 1-Deterministic P Systems. In: Wang, L. (eds) Computing and Combinatorics. COCOON 2005. Lecture Notes in Computer Science, vol 3595. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11533719_91
Download citation
DOI: https://doi.org/10.1007/11533719_91
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28061-3
Online ISBN: 978-3-540-31806-4
eBook Packages: Computer ScienceComputer Science (R0)