P systems with active membranes operating under minimal parallelism
作者： Pierluigi Frisco , Gordon Govan
DOI: 10.1007/978-3-642-28024-5_12
关键词: Theoretical computer science 、 Membrane 、 Mathematics 、 Time complexity 、 Exponential space 、 True quantified Boolean formula 、 Conjunctive normal form 、 Parallel computing 、 Parallelism (grammar)
摘要: We prove that P systems with active membranes operating under minimal parallelism are able to solve NP-complete and PP-complete problems in linear time exponential space when using different types of rules. also these can simulate register machines.
springer.com
sci-hub.st 参考文章(14)
Gheorghe Paun, Arto Salomaa, Grzegorz Rozenberg, The Oxford Handbook of Membrane Computing ,(2010)
Pierluigi Frisco, Computing with Cells: Advances in Membrane Computing ,(2009)
Tseren-Onolt Ishdopj, Power and efficiency of minimal parallelism in polarizationless P systems Journal of Automata, Languages and Combinatorics. ,vol. 11, pp. 299- 320 ,(2006)
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
Marvin L. Minsky, Computation: Finite and Infinite Machines ,(1967)
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
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
Gheorghe Paun, Membrane Computing: An Introduction ,(2002)
J. Van Leeuwen, Handbook of theoretical computer science ,(1990)