Abstract
We look at 1-region membrane computing systems which only use rules of the form Ca →Cv, where C is a catalyst, a is a noncatalyst, and v is a (possibly null) string of noncatalysts. There are no rules of the form a →v. Thus, we can think of these systems as “purely” catalytic. We consider two types: (1) when the initial configuration contains only one catalyst, and (2) when the initial configuration contains multiple (not necessarily distinct) catalysts. We show that systems of the first type are equivalent to communication-free Petri nets, which are also equivalent to commutative context-free grammars. They define precisely the semilinear sets. This partially answers an open question in [19]. Systems of the second type define exactly the recursively enumerable sets of tuples (i.e., Turing machine computable). We also study an extended model where the rules are of the form q: (p, Ca →Cv) (where q and p are states), i.e., the application of the rules is guided by a finite-state control. For this generalized model, type (1) as well as type (2) with some restriction correspond to vector addition 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
Baker, H.G.: Rabin’s proof of the undecidability of the reachability set inclusion problem for vector addition systems. In: C.S.C. Memo 79, Project MAC, MIT (1973)
Berry, G., Boudol, G.: The chemical abstract machine. In: POPL 1990, pp. 81–94. ACM Press, New York (1990)
Bottoni, P., Martin-Vide, C., Paun, G., Rozenberg, G.: Membrane systems with promoters/inhibitors. Acta Informatica 38(10), 695–720 (2002)
Dassow, J., Paun, G.: On the power of membrane computing. Journal of Universal Computer Science 5(2), 33–49 (1999)
Esparza, J.: Petri nets, commutative context-free grammars, and basic parallel processes. In: Reichel, H. (ed.) FCT 1995. LNCS, vol. 965, pp. 221–232. Springer, Heidelberg (1995)
Freund, R., Oswald, M.: P Systems with activated/prohibited membrane channels. In: Păun, G., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) WMC 2002. LNCS, vol. 2597, pp. 261–269. Springer, Heidelberg (2003)
Freund, R., Oswald, M., Sosik, P.: Reducing the number of catalysts needed in computationally universal P systems without priorities. In: the 5th Descriptional Complexity of Formal Systems Workshop (DFCS), July 12-14, Budapest, Hungary (2003)
Frisco, P., Jan Hoogeboom, H.: Simulating counter automata by P Systems with symport/antiport. In: Păun, G., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) WMC 2002. LNCS, vol. 2597, pp. 288–301. Springer, Heidelberg (2003)
Hack, M.H.: The equality problem for vector addition systems is undecidable. In: C.S.C. Memo 121, Project MAC, MIT (1975)
Hopcroft, J., Pansiot, J.-J.: On the reachability problem for 5-dimensional vector addition systems. TCS 8(2), 135–159 (1979)
Huynh, D.T.: Commutative grammars: The complexity of uniform word problems. Information and Control 57, 21–39 (1983)
Martin-Vide, C., Paun, G.: Computing with membranes (P Systems): Universality results. In: Margenstern, M., Rogozhin, Y. (eds.) MCU 2001. LNCS, vol. 2055, pp. 82–101. Springer, Heidelberg (2001)
Mayr, E.: Persistence of vector replacement systems is decidable. Acta Informatica 15, 309–318 (1981)
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)
Parikh, R.: On context-free languages. Journal of the ACM 13, 570–581 (1966)
Paun, G.: Computing with membranes. JCSS 61(1), 108–143 (2000)
Paun, G.: Computing with membranes (P Systems): A variant. International Journal of Foundations of Computer Science 11(1), 167–181 (2000)
Paun, G., Rozenberg, G.: A guide to membrane computing. TCS 287(1), 73–100 (2002)
Sosik, P., Freund, R.: P Systems without priorities are computationally universal. In: Păun, G., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) WMC 2002. LNCS, vol. 2597, pp. 400–409. Springer, Heidelberg (2003)
van Leeuwen, J.: A partial solution to the reachability problem for vector addition systems. In: Andersson, S.I. (ed.) Analysis of Dynamical and Cognitive Systems. LNCS, vol. 888, pp. 303–309. Springer, Heidelberg (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ibarra, O.H., Dang, Z., Egecioglu, O., Saxena, G. (2003). Characterizations of Catalytic Membrane Computing Systems. In: Rovan, B., Vojtáš, P. (eds) Mathematical Foundations of Computer Science 2003. MFCS 2003. Lecture Notes in Computer Science, vol 2747. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45138-9_42
Download citation
DOI: https://doi.org/10.1007/978-3-540-45138-9_42
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40671-6
Online ISBN: 978-3-540-45138-9
eBook Packages: Springer Book Archive