On the Universality of Colored One-Catalyst P Systems

• Autorzy: Wu T. , Zhang Z. , Paun G. , Pan L.

Identyfikatory

DOI

10.3233/FI-2016-1328

• Języki publikacji: EN

Abstrakty

EN

A control strategy on the computations in a one-catalyst P system is provided: the rules are assumed “colored” and in each step only rules of the same “color” are used. Such control leads to Turing universality for one-catalyst P systems with one membrane. Turing universality is also reached for purely catalytic P systems with two catalysts, and for purely catalytic P systems with only one catalyst and cooperating rules working in the so-called terminal mode.

Słowa kluczowe

EN

bio-inspired computing; membrane computing; catalytic P system; catalyst; universality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 144, nr 2
• Strony: 205--212
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Wu T.

• Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China

autor

Zhang Z.

• Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China

autor

Paun G.

• Institute of Mathematics of the Romanian Academ, PO Box 1-764, 014700 Bucuresti, Romania

autor

Pan L.

• Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China

Bibliografia

• [1] Pǎun G. Computing with membranes. Journal of Computer and System Sciences. 2000;61:108–143. See also TUCS Report 208. Available from: www.tucs.fi.
• [2] Freund R, Kari L, Oswald M, Sosík P. Computationally universal P systems without priorities: two catalysts are sufficient. Theoretical Computer Science. 2005;330:251–266.
• [3] Freund R, Sosík P. On the power of catalytic P systems with one catalyst. In: Proceedings of the 16th International Conference on Membrane Computing, 17-21 August, Valencia, Spain, accepted. Springer, LNCS; 2015. Available from: http://users.dsic.upv.es/workshops/cmc16/index/html.
• [4] The Oxford Handbook of Membrane Computing. Gh. Pǎun, G. Rozenberg, A. Salomaa (Eds.). Oxford University Press, Oxford; 2010. ISBN: 0199556679.
• [5] Freund R, Pǎun G. Universal P systems: One catalyst can be sufficient. In: Proceedings of the 11th International Conference Brainstorming Week on Membrane Computing, February 4-8, Seville, Spain; 2013. p. 81–96. ISBN:78-84-940691-9-2. Available from: http://www.fenixeditora.com.
• [6] Pǎun G. Some open problems about catalytic, numerical and spiking neural P systems. In: Proceedings of the 14th International Conference on Membrane Computing, August 20-24, 2013, Chişinǎu, Moldova, Alhazov et al. (eds.). vol. 8340. LNCS, Springer; 2014. p. 33–39. doi:10.1007/978-3-642-54239-8 4.
• [7] Ibarra OH, Dang Z, Egecioglu O. Catalytic P systems, semilinear sets, and vector addition systems. Theoretical Computer Science. 2004;312:379–399. doi:10.1016/j.tcs.2003.10.028.
• [8] Ibarra OH, Dang Z, Egecioglu O, Saxena G. Characterizations of catalytic membrane computing. In: Proceedings of the 28th International Symposium Mathematical Foundations of Computer Science, August 25-29, 2003, Bratislava, Slovakia. Proceedings B. Rovan, P. Vojtás, (eds.). vol. 2747. LNCS, Springer; 2003. p. 480–489. doi:10.1007/978-3-540-45138-9 42.
• [9] Freund R. Purely catalytic P systems: Two catalysts can be sufficient for computational completeness. In: Pre-Proc. 14th International Conference on Membrane Computing, August 20-24. Chişinǎu, Moldova; 2013. p. 153–166. ISBN:978-9975-4237-2-4. Available from: http://www.math.md.
• [10] Pan L, Pǎun G. On the universality of purely catalytic P systems. 2015; Submitted.
• [11] Metta VP, Raghuraman S, Krithivasan K. Spiking neural P systems with cooperating rules. In: Proceedings of the 15th International Conference on Membrane Computing, August 2014, Prague, M. Gheorghe et al. (eds.). vol. 9861. LNCS, Springer; 2014. p. 314–329. ISBN:978-3-319-14370-5. doi:10.1007/978-3-319-14370-5 20.
• [12] Csuhaj-Varjú E, Dassow J, Kelemen J, Pǎun G. Grammar Systems: A Grammatical Approcah to Distribution and Cooperation. Springer Berlin Heidelberg; 1994. doi:10.1007/3-540-60084-1 94.
• [13] Pǎun G. Membrane Computing. An Introduction. In: Natural Computing Series. Springer-Verlag, Berlin; 2002. doi:10.1007/978-3-642-56196-2.
• [14] Minsky ML. Computation: Finite and Infinite Machines. Prentice–Hall, Englewood Cliffs, N.J.; 1967. ISBN-13:978-0131655638.