Abstract
We look at a restricted model of a communicating P system, called RCPS, whose environment does not contain any object initially. The system can expel objects into the environment but only expelled objects can be retrieved from the environment. Such a system is initially given an input \(a_1^{i_1} ... a_n^{i_n}\) (with each i j representing the multiplicity of distinguished object a i , 1 ≤ i ≤ n) and is used as an acceptor. We show that RCPS’s are equivalent to two-way multihead finite automata over bounded languages (i.e., subsets of \(a_1^* ... a_n^*\), for some distinct symbols a 1, ..., a n ). We then show that there is an infinite hierarchy of RCPS’s in terms of the number of membranes. In fact, for every r, there is an s> r and a unary language L accepted by an RCPS with s membranes that cannot be accepted by an RCPS with r membranes. This provides an answer to an open problem in [12] which asks whether there is a nonuniversal model of a membrane computing system which induces an infinite hierarchy on the number of membranes. We also consider variants/generalizations of RCPS’s, e.g., acceptors of languages; models that allow a “polynomial bounded” supply of objects in the environment initially; models with tentacles, etc. We show that they also form an infinite hierarchy with respect to the number of membranes (or tentacles). The proof techniques can be used to obtain similar results for other restricted models of P systems, like symport/antiport systems.
This research was supported in part by NSF Grants IIS-0101134 and CCR02-08595.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berry, G., Boudol, G.: The chemical abstract machine. In: POPL 1990, pp. 81–94. ACM Press, New York (1990)
Csuhaj-Varju, E., Vaszil, G.: P automata. In: Păun, G., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) WMC 2002. LNCS, vol. 2597, pp. 177–192. Springer, Heidelberg (2002)
Freund, R.: Special variants of P systems inducing an infinite hierarchy with respect to the number of membranes. Bulletin of the EATCS (75), 209–219 (2001)
Freund, R., Oswald, M.: A short note on analyzing P systems with antiport rules. Bulletin of EATCS 78, 231–236 (2002)
Ibarra, O.H., Dang, Z., Egecioglu, O., Saxena, G.: Characterizations of catalytic membrane computing systems. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 480–489. Springer, Heidelberg (2003)
Ibarra, O.H.: On the computational complexity of membrane computing systems (2003) (submitted)
Krishna, S.: Infinite hierarchies on some variants of P systems (2002) (submitted)
Monien, B.: Two-way multihead automata over a one-letter alphabet. RAIRO Informatique theorique 14(1), 67–82 (1980)
Paun, A., Paun, G.: The power of communication: P systems with symport/ antiport. New Generation Computing 20(3), 295–306 (2002)
Paun, Gh.: List of problems circulated before the Brainstorming Week in Membrane Computing held in Tarragona, Spain, February 5-11 (2003)
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)
Paun, Gh., Perez-Jimenez, M., Sancho-Caparrini, F.: On the reachability problem for P systems with symport/antiport (2002) (submitted)
Paun, G., Rozenberg, G.: A guide to membrane computing. TCS 287(1), 73–100 (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–376. Springer, Heidelberg (2003)
Sosik, P., Matysek, J.: Membrane computing: when communication is enough. In: Calude, C.S., Dinneen, M.J., Peper, F. (eds.) UMC 2002. LNCS, vol. 2509, pp. 264–275. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ibarra, O.H. (2004). The Number of Membranes Matters. In: Martín-Vide, C., Mauri, G., Păun, G., Rozenberg, G., Salomaa, A. (eds) Membrane Computing. WMC 2003. Lecture Notes in Computer Science, vol 2933. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24619-0_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-24619-0_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20895-2
Online ISBN: 978-3-540-24619-0
eBook Packages: Springer Book Archive