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

Subroutines in P Systems and Closure Properties of Their Complexity Classes

Opened Access Subroutines in P Systems and Closure Properties of Their Complexity Classes
Estadísticas
Icon
Exportar a
Autor: Leporati, Alberto
Manzoni, Luca
Mauri, Giancarlo
Porreca, Antonio E.
Zandron, Claudio
Fecha: 2017
Publicado en: BWMC 2017: 15th Brainstorming Week on Membrane Computing (2017), p 115-128
ISBN/ISSN: 978-84-946316-9-6
Tipo de documento: Ponencia
Resumen: The literature on membrane computing describes several variants of P systems whose complexity classes C are "closed under exponentiation", that is, they satisfy the inclusion PC C, where PC is the class of problems solved by polynomial-time Turing machines with oracles for problems in C. This closure automatically implies closure under many other operations, such as regular operations (union, concatenation, Kleene star), intersection, complement, and polynomial-time mappings, which are inherited from P. Such results are typically proved by showing how elements of a family of P systems can be embedded into P systems simulating Turing machines, which exploit the elements of as subroutines. Here we focus on the latter construction, abstracting from the technical details which depend on the speci c variant of P system, in order to describe a general strategy for proving closure under exponentiation.
Cita: Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E. y Zandron, C. (2017). Subroutines in P Systems and Closure Properties of Their Complexity Classes. En BWMC 2017: 15th Brainstorming Week on Membrane Computing (115-128), Sevilla, España: Fenix Editora.
Tamaño: 380.7Kb
Formato: PDF

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

Ver versión del editor

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