Monodirectional P Systems
Porreca, Antonio E.
|Published in||Proceedings of the Thirteenth Brainstorming Week on Membrane Computing, 207-226. Sevilla, E.T.S. de Ingeniería Informática, 2-6 de Febrero, 2015,|
|Abstract||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.|