Complexity Classes for Membrane Systems: A Survey
作者： Giancarlo Mauri , Alberto Leporati , Luca Manzoni , Antonio E. Porreca , Claudio Zandron
DOI: 10.1007/978-3-319-15579-1_4
关键词:
摘要: The computational power of membrane systems, in their different variants, can be studied by defining classes problems that solved within given bounds on computation time or space, and comparing them with usual complexity related to the Turing Machine model. Here we will consider particular systems active membranes (where new created division existing membranes). definition time/space for discussed, resulting hierarchy compared classes, mainly through simulations Machines (uniform families of) membranes.
springer.com
units.it参考文章(22)
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
Gheorghe Paun, Arto Salomaa, Grzegorz Rozenberg, The Oxford Handbook of Membrane Computing ,(2010)
Antonio E. Porreca, Alberto Leporati, Giancarlo Mauri, Claudio Zandron, Introducing a Space Complexity Measure for P Systems International Journal of Computers Communications & Control. ,vol. 4, pp. 301- 310 ,(2009) , 10.15837/IJCCC.2009.3.2779
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
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
Gheorghe Păun, P systems with active membranes: attacking NP-complete problems Journal of Automata, Languages and Combinatorics. ,vol. 6, pp. 75- 90 ,(2001)
Artiom Alhazov, Carlos Martín-Vide, Linqiang Pan, Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes Fundamenta Informaticae. ,vol. 58, pp. 67- 77 ,(2003)
Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron, Constant-Space P Systems with Active Membranes Fundamenta Informaticae. ,vol. 134, pp. 111- 128 ,(2014) , 10.3233/FI-2014-1094
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
Andrea Valsecchi, Antonio E. Porreca, Alberto Leporati, Giancarlo Mauri, Claudio Zandron, An efficient simulation of polynomial-space turing machines by p systems with active membranes international conference on membrane computing. pp. 461- 478 ,(2009) , 10.1007/978-3-642-11467-0_31