Opened Access Monodirectional P Systems
Exportar a
Autor: Leporati, Alberto
Manzoni, Luca
Mauri, Giancarlo
Porreca, Antonio E.
Zandron, Claudio
Fecha: 2015
Publicado en: Proceedings of the Thirteenth Brainstorming Week on Membrane Computing, 207-226. Sevilla, E.T.S. de Ingeniería Informática, 2-6 de Febrero, 2015,
ISBN/ISSN: 978-84-944366-2-8
Tipo de documento: Ponencia
Resumen: We investigate the in uence that the ow of information in membrane systems has on their computational complexity. In particular, we analyse the behaviour of P systems with active membranes where communication only happens from a membrane towards its parent, and never in the opposite direction. We prove that these \monodirectional P systems" are, when working in polynomial time and under standard complexity-theoretic assumptions, much less powerful than unrestricted ones: indeed, they characterise classes of problems de ned by polynomial-time Turing machines with NP oracles, rather than the whole class PSPACE of problems solvable in polynomial space.
Tamaño: 366.9Kb
Formato: PDF


Mostrar el registro completo del ítem

Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones