Journal
NATURAL COMPUTING
Volume 15, Issue 4, Pages 551-564Publisher
SPRINGER
DOI: 10.1007/s11047-016-9565-2
Keywords
-
Categories
Funding
- Universita degli Studi di Milano-Bicocca, FA: Complessita computazionale nei sistemi a membrane''
Ask authors/readers for more resources
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 oracles, rather than the whole class of problems solvable in polynomial space.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available