We investigate the influence that the flow of information in membrane systems has on their computational complexity. In particular, we analyse the behaviour of P systems with active membranes where communication only happens from a membrane towards its parent, and never in the opposite direction. We prove that these “monodirectional P systems” are, when working in polynomial time and under standard complexity-theoretic assumptions, much less powerful than unrestricted ones: indeed, they characterise classes of problems defined by polynomial-time Turing machines with NP oracles, rather than the whole class PSPACE of problems solvable in polynomial space.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2016). Monodirectional P systems. NATURAL COMPUTING, 15(4), 551-564 [10.1007/s11047-016-9565-2].
Citazione: | Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2016). Monodirectional P systems. NATURAL COMPUTING, 15(4), 551-564 [10.1007/s11047-016-9565-2]. | |
Tipo: | Articolo in rivista - Articolo scientifico | |
Carattere della pubblicazione: | Scientifica | |
Presenza di un coautore afferente ad Istituzioni straniere: | No | |
Titolo: | Monodirectional P systems | |
Autori: | Leporati, A; Manzoni, L; Mauri, G; Porreca, A; Zandron, C | |
Autori: | MANZONI, LUCA (Secondo) PORRECA, ANTONIO ENRICO (Penultimo) ZANDRON, CLAUDIO (Ultimo) | |
Data di pubblicazione: | 2016 | |
Lingua: | English | |
Rivista: | NATURAL COMPUTING | |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/s11047-016-9565-2 | |
Appare nelle tipologie: | 01 - Articolo su rivista |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
Paper.pdf | Preprint | N/A | Open Access Visualizza/Apri | |
Monodirectional P Systems - NaCo (2016).pdf | Publisher's version | Administrator Richiedi una copia |