We give a characterisation of the class of problems solved in polynomial time by uniform and semi-uniform families of P systems with active membranes, using matter/antimatter annihilation rules and elementary membrane division. Like several other variants of P systems with elementary division, this class is exactly P#P, that is, the problems solvable efficiently with access to oracles for counting problems. We also consider the monodirectional case, where objects in the P system can only move from inner regions towards outer regions. In that case, the above model of P systems characterises the class P∥#P, where each query is independent of the result of the others; this contrasts with traditional P systems with active membranes, which characterise the (conjecturally proper) subclass P∥NP
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2017). The counting power of P systems with antimatter. THEORETICAL COMPUTER SCIENCE, 701, 161-173 [10.1016/j.tcs.2017.03.045].
Citazione: | Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2017). The counting power of P systems with antimatter. THEORETICAL COMPUTER SCIENCE, 701, 161-173 [10.1016/j.tcs.2017.03.045]. | |
Tipo: | Articolo in rivista - Articolo scientifico | |
Carattere della pubblicazione: | Scientifica | |
Presenza di un coautore afferente ad Istituzioni straniere: | No | |
Titolo: | The counting power of P systems with antimatter | |
Autori: | Leporati, A; Manzoni, L; Mauri, G; Porreca, A; Zandron, C | |
Autori: | ||
Data di pubblicazione: | 2017 | |
Lingua: | English | |
Rivista: | THEORETICAL COMPUTER SCIENCE | |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.tcs.2017.03.045 | |
Appare nelle tipologie: | 01 - Articolo su rivista |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
The counting power of P systems with antimatter (TCS 2017).pdf | Publisher's version | Administrator Richiedi una copia |