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

Standardized Proofs of PSPACE-completeness of P Systems with Active Membranes

Opened Access Standardized Proofs of PSPACE-completeness of P Systems with Active Membranes
Estadísticas
Icon
Exportar a
Autor: Sosík, Petr
Rodríguez Patón, Alfonso
Ciencialová, Lucie
Fecha: 2010
Publicado en: Proceedings of the Eighth Brainstorming Week on Membrane Computing, 301-310. Sevilla, E.T.S. de Ingeniería Informática, 1-5 de Febrero, 2010
ISBN/ISSN: 9788461423576
Tipo de documento: Ponencia
Resumen: Two proofs have been shown for P systems with active membranes in previ- ously published papers, demonstrating that these P systems can solve in polynomial time exactly the class of problems PSPACE. Consequently, these P systems are equivalent (up to a polynomial time reduction) to Second Machine Class models as the alternating Turing machine or the PRAM computer. These proofs were based on a modified definition of uniform families of P systems. Here we demonstrate that the results remain valid also in the case of standard definitions.
Tamaño: 172.2Kb
Formato: PDF

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

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