Asynchronous P systems with active membranes
作者： Pierluigi Frisco , Gordon Govan , Alberto Leporati
DOI: 10.1016/J.TCS.2011.12.026
关键词:
摘要: We prove that recognising P systems with active membranes operating in asynchronous mode are able to solve a semi-uniform way both NP-complete and PP-complete problems linear time (in the best case) exponential space, when using different sets of rules. Precisely, proposed solution k-SAT, k>=3, uses evolution communication rules, as well creation division non-elementary membranes; however, it does not use neither polarisations nor membrane dissolution Our MAJORITY-SAT makes together rules for dividing membranes. also these can simulate partially blind register machines; converse simulation holds constrained version our systems.
core.ac.uk
elsevier.com
sci-hub.se 参考文章(15)
Gheorghe Paun, Arto Salomaa, Grzegorz Rozenberg, The Oxford Handbook of Membrane Computing ,(2010)
Pierluigi Frisco, Computing with Cells: Advances in Membrane Computing ,(2009)
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
Antonio E. Porreca, Alberto Leporati, Giancarlo Mauri, Claudio Zandron, P systems with elementary active membranes: beyond NP and coNP international conference on membrane computing. pp. 338- 347 ,(2010) , 10.1007/978-3-642-18123-8_26
Mario J. Pérez-Jiménez, Alvaro Romero-Jiménez, Fernando Sancho-Caparrini, Computationally Hard Problems Addressed Through P Systems Applications of Membrane Computing. pp. 315- 346 ,(2006) , 10.1007/3-540-29937-8_12
Pierluigi Frisco, Gordon Govan, P systems with active membranes operating under minimal parallelism international conference on membrane computing. pp. 165- 181 ,(2011) , 10.1007/978-3-642-28024-5_12
Niall Murphy, Damien Woods, The computational power of membrane systems under tight uniformity conditions Natural Computing. ,vol. 10, pp. 613- 632 ,(2011) , 10.1007/S11047-010-9244-7
Gabriel Ciobanu, Linqiang Pan, Gheorghe Păun, Mario J. Pérez-Jiménez, P systems with minimal parallelism Theoretical Computer Science. ,vol. 378, pp. 117- 130 ,(2007) , 10.1016/J.TCS.2007.03.044
Pierluigi Frisco, The conformon-P system: a molecular and cell biology-inspired computability model Theoretical Computer Science. ,vol. 312, pp. 295- 319 ,(2004) , 10.1016/J.TCS.2003.09.008
Antonio E. Porreca, Alberto Leporati, Giancarlo Mauri, Claudio Zandron, Elementary Active Membranes Have the Power of Counting International Journal of Natural Computing Research. ,vol. 2, pp. 35- 48 ,(2011) , 10.4018/JNCR.2011070104