Characterising the complexity of tissue P systems with fission rules
作者： Alberto Leporati , Luca Manzoni , Giancarlo Mauri , Antonio E. Porreca , Claudio Zandron
DOI: 10.1016/J.JCSS.2017.06.008
关键词:
摘要: Abstract We analyse the computational efficiency of tissue P systems, a biologically-inspired computing device modelling communication between cells. In particular, we focus on systems with fission rules (cell division and/or cell separation), where number cells can increase exponentially during computation. prove that complexity class characterised by these devices in polynomial time is exactly # , problems solved polynomial-time Turing machines oracles for counting problems.
units.it参考文章(18)
Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron, Simulating Elementary Active Membranes Membrane Computing. ,vol. 8961, pp. 284- 299 ,(2014) , 10.1007/978-3-319-14370-5_18
Petr Sosík, The computational power of cell division in P systems: Beating down parallel computers? Natural Computing. ,vol. 2, pp. 287- 298 ,(2003) , 10.1023/A:1025401325428
Gheorghe Păun, P systems with active membranes: attacking NP-complete problems Journal of Automata, Languages and Combinatorics. ,vol. 6, pp. 75- 90 ,(2001)
Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron, Membrane Division, Oracles, and the Counting Hierarchy Fundamenta Informaticae. ,vol. 138, pp. 97- 111 ,(2015) , 10.3233/FI-2015-1201
Petr Sosík, Luděk Cienciala, Computational power of cell separation in tissue P systems Information Sciences. ,vol. 279, pp. 805- 815 ,(2014) , 10.1016/J.INS.2014.04.031
Seinosuke Toda, Simple characterizations of P(#P) and complete problems Journal of Computer and System Sciences. ,vol. 49, pp. 1- 17 ,(1994) , 10.1016/S0022-0000(05)80082-0
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
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
Klaus W. Wagner, The complexity of combinatorial problems with succinct input representation Acta Informatica. ,vol. 23, pp. 325- 356 ,(1986) , 10.1007/BF00289117
Mario J. Pérez-Jiménez, The P versus NP Problem from the Membrane Computing View European Review. ,vol. 22, pp. 18- 33 ,(2014) , 10.1017/S1062798713000598