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

The Computational Power of Exponential-Space P Systems with Active Membranes

Opened Access The Computational Power of Exponential-Space P Systems with Active Membranes
Estadísticas
Icon
Exportar a
Autor: Alhazov, Artiom
Leporati, Alberto
Mauri, Giancarlo
Porreca, Antonio E.
Zandron, Claudio
Fecha: 2012
Publicado en: Proceedings of the Tenth Brainstorming Week on Membrane Computing, 35-60. Sevilla, E.T.S. de Ingeniería Informática, 30 de Enero-3 de Febrero, 2012,
ISBN/ISSN: 978-84-940056-5-7
Tipo de documento: Ponencia
Resumen: We show that exponential-space P systems with active membranes characterize the complexity class EXPSPACE. This result is proved by simulating Turing machines working in exponential space via uniform families of P systems with restricted elementary active membranes; the simulation is e cient, in the sense that the time and space required are at most polynomial with respect to the resources employed by the simulated Turing machine.
Tamaño: 483.9Kb
Formato: PDF

URI: http://hdl.handle.net/11441/33939

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