Published January 29, 2016
| Version v1
Publication
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
Identifiers
- URL
- https://idus.us.es/handle/11441/33541
- URN
- urn:oai:idus.us.es:11441/33541