dc.creator | Leporati, Alberto | es |
dc.creator | Manzoni, Luca | es |
dc.creator | Mauri, Giancarlo | es |
dc.creator | Porreca, Antonio E. | es |
dc.creator | Zandron, Claudio | es |
dc.date.accessioned | 2017-12-18T09:37:03Z | |
dc.date.available | 2017-12-18T09:37:03Z | |
dc.date.issued | 2017 | |
dc.identifier.citation | 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. | |
dc.identifier.isbn | 978-84-946316-9-6 | es |
dc.identifier.uri | http://hdl.handle.net/11441/67736 | |
dc.description.abstract | 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. | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Fenix Editora | es |
dc.relation.ispartof | BWMC 2017: 15th Brainstorming Week on Membrane Computing (2017), p 115-128 | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Subroutines in P Systems and Closure Properties of Their Complexity Classes | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.relation.publisherversion | http://www.gcn.us.es/15bwmc_proceedings | es |
idus.format.extent | 14 | es |
dc.publication.initialPage | 115 | es |
dc.publication.endPage | 128 | es |
dc.eventtitle | BWMC 2017: 15th Brainstorming Week on Membrane Computing | es |
dc.eventinstitution | Sevilla, España | es |
dc.relation.publicationplace | Sevilla | es |