Ponencia
Subroutines in P Systems and Closure Properties of Their Complexity Classes
Autor/es | Leporati, Alberto
Manzoni, Luca Mauri, Giancarlo Porreca, Antonio E. Zandron, Claudio |
Fecha de publicación | 2017 |
Fecha de depósito | 2017-12-18 |
Publicado en |
|
ISBN/ISSN | 978-84-946316-9-6 |
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 ... 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
115_SubroutinesClosure.pdf | 380.7Kb | [PDF] | Ver/ | |