Constant-Space P Systems with Active Membranes

Description

We continue the investigation of the computational power of space- constrained P systems. We show that only a constant amount of space is needed in order to simulate a polynomial-space bounded Turing machine. Due to this result, we propose an alternative de nition of space complexity for P systems, where the amount of information contained in individual objects and membrane labels is also taken into ac- count. Finally, we prove that, when less than a logarithmic number of membrane labels is available, moving the input objects around the membrane structure without rewriting them is not enough to even distinguish inputs of the same length.

Additional details