Ponencia
Monodirectional P Systems
Autor/es | Leporati, Alberto
Manzoni, Luca Mauri, Giancarlo Porreca, Antonio E. Zandron, Claudio |
Fecha de publicación | 2015 |
Fecha de depósito | 2016-01-22 |
Publicado en |
|
ISBN/ISSN | 978-84-944366-2-8 |
Resumen | We investigate the in
uence that the
ow 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 ... We investigate the in uence that the ow 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 de ned by polynomial-time Turing machines with NP oracles, rather than the whole class PSPACE of problems solvable in polynomial space. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
207_Paper.pdf | 366.9Kb | [PDF] | Ver/ | |