Characterizing tractability by tissue-like p systems
作者： Rosa Gutiérrez–Escudero , Mario J. Pérez–Jiménez , Miquel Rius–Font
DOI: 10.1007/978-3-642-11467-0_21
关键词:
摘要: In the framework of recognizer cell–like membrane systems it is well known that construction exponential number objects in polynomial time not enough to efficiently solve NP–complete problems. Nonetheless, may be sufficient create an membranes time. In this paper, we study computational efficiency tissue P with communication (symport/antiport) rules and division rules. Some results have been already obtained direction: (a) using making no use rules, only tractable problems can solved; (b) length three solved. show plays a relevant role from point view for kind systems.
unirioja.es
springer.com
us.es
core.ac.uk 
sci-hub.st 参考文章(16)
Álvaro Romero Jiménez, Fernando Sancho-Caparrini, Mario J. Pérez-Jiménez, A Polynomial Complexity Class in P Systems Using Membrane Division. DCFS. pp. 284- 294 ,(2003)
Miguel A. Gutiérrez–Naranjo, Mario J. Pérez–Jiménez, Agustín Riscos–Núñez, Francisco J. Romero–Campero, On the Power of Dissolution in P Systems with Active Membranes Membrane Computing. pp. 224- 240 ,(2006) , 10.1007/11603047_16
Pierluigi Frisco, Hendrik Jan Hoogeboom, Simulating Counter Automata by P Systems with Symport/Antiport Lecture Notes in Computer Science. pp. 288- 301 ,(2002) , 10.1007/3-540-36490-0_19
Mario J. Péerez Jiménez, Álvaro Romero Jiménez, Fernando Sancho Caparrini, Complexity classes in models of cellular computing with membranes Natural Computing. ,vol. 2, pp. 265- 285 ,(2003) , 10.1023/A:1025449224520
Andrei Pâun, Gheorghe Pâun, The power of communication: P systems with symport/antiport New Generation Computing. ,vol. 20, pp. 295- 305 ,(2002) , 10.1007/BF03037362
Fernando Sancho Caparrini, Álvaro Romero Jiménez, Mario J. Pérez Jiménez, A polynomial complexity class in P systems using membrane division Journal of Automata, Languages and Combinatorics. ,vol. 11, pp. 423- 434 ,(2006) , 10.5555/1993417.1993421
Carlos Martín-Vide, Gheorghe Păun, Juan Pazos, Alfonso Rodríguez-Patón, Tissue P systems Theoretical Computer Science. ,vol. 296, pp. 295- 326 ,(2003) , 10.1016/S0304-3975(02)00659-X
Daniel Díaz-Pernil, Mario J. Pérez-Jiménez, Álvaro Romero-Jiménez, Efficient simulation of tissue-like P systems by transition cell-like P systems Natural Computing. ,vol. 8, pp. 797- 806 ,(2009) , 10.1007/S11047-008-9102-Z
Gheorghe Paun, Membrane Computing: An Introduction ,(2002)
Gheorghe Păun, Computing with Membranes Journal of Computer and System Sciences. ,vol. 61, pp. 108- 143 ,(2000) , 10.1006/JCSS.1999.1693