Ponencia
Constant-Space P Systems with Active Membranes
Autor/es | Leporati, Alberto
Manzoni, Luca Mauri, Giancarlo Porreca, Antonio E. Zandron, Claudio |
Fecha de publicación | 2014 |
Fecha de depósito | 2016-01-29 |
Publicado en |
|
ISBN/ISSN | 978-84-940056-4-0 |
Resumen | 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 ... 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
243_Paper.pdf | 313.7Kb | [PDF] | Ver/ | |