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 [10.1016/j.jcss.2017.06.008].
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 [10.1016/j.jcss.2017.06.008]. | |
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 |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
JCSSVers.pdf | Publisher's version | Administrator Richiedi una copia |