Efficient simulation of tissue-like P systems by transition cell-like P systems

被引：13

作者：

Díaz-Pernil D. ^{[1
]}

Pérez-Jiménez M.J. ^{[1
]}

Romero-Jiménez Á. ^{[1
]}

机构：

[1] Department of Computer Science and Artificial Intelligence, Research Group on Natural Computing, University of Sevilla, Sevilla

来源：

Natural Computing | 2009年 / 8卷 / 4期

关键词：

Efficient simulation of cellular systems; P systems; Recognizer P systems; Symport/antiport rules; Tissue P systems;

D O I：

10.1007/s11047-008-9102-z

中图分类号：

学科分类号：

摘要：

In the framework of P systems, it is known that the construction of exponential number of objects in polynomial time is not enough to efficiently solve NP-complete problems. Nonetheless, it could be sufficient to create an exponential number of membranes in polynomial time. Working with P systems whose membrane structure does not increase in size, it is known that it is not possible to solve computationally hard problems (unless P = NP), basically due to the impossibility of constructing exponential number of membranes, in polynomial time, using only evolution, communication and dissolution rules. In this paper we show how a family of recognizer tissue P systems with symport/antiport rules which solves a decision problem can be efficiently simulated by a family of basic recognizer P systems solving the same problem. This simulation allows us to transfer the result about the limitations in computational power, from the model of basic cell-like P systems to this kind of tissue-like P systems. © 2008 Springer Science+Business Media B.V.

引用

页码：797 / 806

页数：9

共 9 条

[1]

Diaz-Pernil D., Sistemas Celulares de Tejidos: Formalización y Eficiencia Computacional, (2008)

[2]

Gutierrez-Naranjo M.A., Perez-Jimenez M.J., Riscos-Nunez A., Romero-Campero F.J., Romero-Jimenez A., Characterizing tractability by cell-like membrane systems, Formal Models, Languages and Applications. World Scientific, Series in Machine Perception and Artificial Intelligence, 66, pp. 137-154, (2006)

[3]

Martin-Vide C., Pazos J., Gh P., Rodriguez Paton A., Tissue P systems, Theor Comput Sci, 296, pp. 295-326, (2003)

[4]

Paun G., Computing with membranes, Journal of Computer and System Sciences, 61, 1, pp. 108-143, (2000)

[5]

Gh P., Membrane Computing. An Introduction, (2002)

[6]

Paun A., Gh P., The power of communication: P systems with symport/antiport, New Generat Comput, 20, 3, pp. 295-305, (2002)

[7]

Gh P., Perez-Jimenez M.J., Recent computing models inspired from biology: DNA and membrane computing, Theoria, 18, 46, pp. 72-84, (2003)

[8]

Gh P., Perez-Jimenez M.J., Riscos-Nunez A., Tissue P systems with cell division, Second Brainstorming Week on Membrane Computing, Sevilla, Report RGNC 01/2004, pp. 380-386, (2004)

[9]

Peerez Jimenez M.J., Romero Jimenez A., Sancho Caparrini F., Complexity classes in models of cellular computing with membranes, Natural Computing, 2, 3, pp. 265-285, (2003)

← 1 →