Bridging Membrane and Reaction Systems : Further Results and Research Topics

• Autorzy: Păun G. , Pérez-Jiménez M.J. , Rozenberg G.
• Języki publikacji: EN

Abstrakty

EN

This paper continues an investigation into bridging two research areas concerned with natural computing: membrane computing and reaction systems. More specifically, the paper considers a transfer of two assumptions/axioms of reaction systems, non-permanency and the threshold assumption, into the framework of membrane computing. It is proved that: (1) spiking neural P systems with non-permanency of spikes assumption characterize the semilinear sets of numbers, and (2) symport/antiport P systems with threshold assumption (translated as ω multiplicity of objects) can solve SAT in polynomial time. Also, several open research problems are stated.

Słowa kluczowe

EN

fypercomputation; Membrane computing; reaction system; SAT; semilinear set

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 127, nr 1-4
• Strony: 99--114
• Opis fizyczny: Bibliogr. 20 poz., rys., tab.

Twórcy

autor

Păun G.

• Institute of Mathematics of the Romanian Academy, PO Box 1-764, 014700 Bucharest, Romania

autor

Pérez-Jiménez M.J.

• Research Group on Natural Computing, Department of Computer Science and AI, University of Sevilla, Avda Reina Mercedes s/n, 41012 Sevilla, Spain

autor

Rozenberg G.

• Leiden Institute for Advanced Computer Science - LIACS, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands

Bibliografia

• [1] R. Brijder, A. Ehrenfeucht, M. Main, G. Rozenberg: A tour of reaction systems. International J. Found. Computer Sci., 22 (2011), 1499-1518.
• [2] J. Copeland: Hypercomputation. Minds and machines, 12, 461-502 (2002)
• [3] A. Ehrenfeucht, J. Kleijn, M. Koutny, G. Rozenberg: Qualitative and quantitative aspects of a model for processes inspired by the functioning of the living cell. Biomolecular Information Processing, From Logic Systems to Smart Sensors and Actuators (E. Katz, ed.), Wiley-VCH, Weinheim, 2012, 303-322.
• [4] A. Ehrenfeucht, G. Rozenberg: Reaction systems. FundamentaInformaticae, 75 (2007), 263-280.
• [5] A. Ehrenfeucht, G. Rozenberg: Events and modules in reaction systems. Theoretical Computer Sci., 376 (2007), 3-16.
• [6] A. Ehrenfeucht, G. Rozenberg: Introducing time in reaction systems. Theoretical Computer Sci. , 410 (2009), 310-322.
• [7] R. Freund, L. Kari, P. Sosik: Computationally universal P systems without priorities: two catalysts are sufficient. Theoretical Computer Sci., 330 (2005), 251-266.
• [8] O.H. Ibarra, A. Pǎun, Gh. Pǎun, A. Rodríguez-Patón, P. Sosik, S. Woodworth: Normal forms for spiking neural P systems. Theoretical Computer Sci., 372 (2007), 196-217.
• [9] M. Ionescu, Gh. Pǎun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 279-308 (2006)
• [10] M. Minsky: Computation - Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967.
• [11] A. Pǎun, Gh. Pǎun: The power of communication: P systems with symport/antiport. New Generation Computing, 20, 3 (2002), 295-306.
• [12] Gh. Pǎun: Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108-143 (first circulated as Turku Center for Computer Science-TUCS Report 208, November 1998, www. tucs. f i).
• [13] Gh. Pǎun: Membrane Computing. An Introduction. Springer, Berlin, 2002.
• [14] Gh. Pǎun: Towards fypercomputations (in membrane computing). Languages Alive. Essays Dedicated to Jurgen Dassow on the Occasion of His 65 Birthday (H. Bordihn, M. Kutrib, B. Truthe, etcs.), LNCS 7300, Springer, Berlin, 2012, 207-221.
• [15] Gh. Pǎun: The “catalytic borderline” between universality and non-universality of P systems. Proc. 11th Brainstorming Week on Membrane Computing, Sevilla, February 2013, Fenix Editora, Sevilla, 2013, 225234.
• [16] Gh. Pǎun, M.J. Perez-Jimenez: Towards bridging two cell-inspired models: P systems and R systems. Theoretical Computer Sci., 429 (2012), 258-264.
• [17] Gh. Pǎun, G. Rozenberg, A. Salomaa, eds.: Handbook of Membrane Computing. Oxford University Press, 2010.
• [18] M.J. Perez-Jimenez: Computational complexity theory in membrane computing (Invited talk). New Frontiers in Informatics. 24th Annual Conference of Academia Europaea, Bergen, Norway, September 11, 2012.
• [19] A. Salomaa: Formal Languages. Academic Press, New York, 1973.
• [20] The P Systems Website: http : //ppage. psystems. eu.