We prove that polynomial-time tissue P systems with cell division or cell separation can be simulated efficiently by Turing machines with oracles for counting problems. This shows that the corresponding complexity classes are included in P#P, thus improving, under standard complexity theory assumptions, the previously known upper bound PSPACE.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2015). Tissue P systems can be simulated efficiently with counting oracles. In 16th International Conference on Membrane Computing, CMC 2015; Valencia; Spain; 17-21 August 2015 (pp.251-261). Springer Verlag.
Citazione: | Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2015). Tissue P systems can be simulated efficiently with counting oracles. In 16th International Conference on Membrane Computing, CMC 2015; Valencia; Spain; 17-21 August 2015 (pp.251-261). Springer Verlag. |
Tipo: | slide + paper |
Carattere della pubblicazione: | Scientifica |
Presenza di un coautore afferente ad Istituzioni straniere: | No |
Titolo: | Tissue P systems can be simulated efficiently with counting oracles |
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 (Corresponding) |
Data di pubblicazione: | 2015 |
Lingua: | English |
Nome del convegno: | 16th International Conference on Membrane Computing, CMC 2015 |
ISBN: | 9783319284743 |
Serie: | LECTURE NOTES IN COMPUTER SCIENCE |
Appare nelle tipologie: | 02 - Intervento a convegno |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
Paper.pdf | Preprint | N/A | Open Access Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.