We analyse the computational efficiency of tissue P systems, a biologically-inspired computing device modelling the communication between cells. In particular, we focus on tissue P systems with fission rules (cell division and/or cell separation), where the number of cells can increase exponentially during the computation. We prove that the complexity class characterised by these devices in polynomial time is exactly P#P, the class of problems solved by polynomial-time Turing machines with oracles for counting problems.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2017). Characterising the complexity of tissue P systems with fission rules. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 90, 115-128.
Citazione: | Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2017). Characterising the complexity of tissue P systems with fission rules. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 90, 115-128. |
Tipo: | Articolo in rivista - Articolo scientifico |
Carattere della pubblicazione: | Scientifica |
Presenza di un coautore afferente ad Istituzioni straniere: | No |
Titolo: | Characterising the complexity of tissue P systems with fission rules |
Autori: | Leporati, A; Manzoni, L; Mauri, G; Porreca, A; Zandron, C |
Autori: | LEPORATI, ALBERTO OTTAVIO (Primo) MANZONI, LUCA (Secondo) PORRECA, ANTONIO ENRICO (Penultimo) ZANDRON, CLAUDIO (Ultimo) |
Data di pubblicazione: | 2017 |
Lingua: | English |
Rivista: | JOURNAL OF COMPUTER AND SYSTEM SCIENCES |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.jcss.2017.06.008 |
Appare nelle tipologie: | 01 - Articolo su rivista |