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 [Formula presented], where [Formula presented] 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 [Formula presented]. Such results are typically proved by showing how elements of a family [Formula presented] of P systems can be embedded into P systems simulating Turing machines, which exploit the elements of [Formula presented] as subroutines. Here we focus on the latter construction, providing a description that, by abstracting from the technical details which depend on the specific variant of P system, describes a general strategy for proving closure under exponentiation. We also provide an example implementation using polarizationless P systems with active membranes and minimal cooperation.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2020). Subroutines in P systems and closure properties of their complexity classes. THEORETICAL COMPUTER SCIENCE, 805, 193-205 [10.1016/j.tcs.2018.06.012].
|Citazione:||Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2020). Subroutines in P systems and closure properties of their complexity classes. THEORETICAL COMPUTER SCIENCE, 805, 193-205 [10.1016/j.tcs.2018.06.012].|
|Tipo:||Articolo in rivista - Articolo scientifico|
|Carattere della pubblicazione:||Scientifica|
|Presenza di un coautore afferente ad Istituzioni straniere:||No|
|Titolo:||Subroutines in P systems and closure properties of their complexity classes|
|Autori:||Leporati, A; Manzoni, L; Mauri, G; Porreca, A; Zandron, C|
LEPORATI, ALBERTO OTTAVIO (Corresponding)
MANZONI, LUCA (Corresponding)
MAURI, GIANCARLO (Corresponding)
ZANDRON, CLAUDIO (Corresponding)
|Data di pubblicazione:||2020|
|Rivista:||THEORETICAL COMPUTER SCIENCE|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1016/j.tcs.2018.06.012|
|Appare nelle tipologie:||01 - Articolo su rivista|