Repositorio de producción científica de la Universidad de Sevilla

Constant-Space P Systems with Active Membranes


Advanced Search
Opened Access Constant-Space P Systems with Active Membranes
Show item statistics
Export to
Author: Leporati, Alberto
Manzoni, Luca
Mauri, Giancarlo
Porreca, Antonio E.
Zandron, Claudio
Date: 2014
Published in: Proceedings of the Twelfth Brainstorming Week on Membrane Computing, 243-260. Sevilla, E.T.S. de Ingeniería Informática, 3-7 de Febrero, 2014,
ISBN/ISSN: 978-84-940056-4-0
Document type: Presentation
Abstract: 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.
Size: 313.7Kb
Format: PDF


This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)