KOLONITS , Gábor

In this paper we consider three restricted variants of P systems with active membranes: (1) P systems using out communication rules only, (2) P systems using elementary membrane division and dissolution rules only, and (3) polarizationless P systems using dissolution and restricted evolution rules only. We show that every problem in P can be...

We prove that every single-tape deterministic Turing machine working in t(n) t(n) time, for some function t:N→N t:N→N , can be simulated by a uniform family of polarizationless P systems with active membranes. Moreover, this is done without significant slowdown in the working time. Furthermore, if logt(n) log⁡t(n) is space constructible,...