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].

Subroutines in P systems and closure properties of their complexity classes

Leporati, A;Manzoni, L
;
Mauri, G;Zandron, C
2020

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 [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.
Articolo in rivista - Articolo scientifico
Closure under exponentiation; Membrane computing; Oracle machines;
English
19-giu-2018
2020
805
193
205
reserved
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].
File in questo prodotto:
File Dimensione Formato  
Leporati-2020-TCS-VoR.pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Licenza: Tutti i diritti riservati
Dimensione 546.15 kB
Formato Adobe PDF
546.15 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/211922
Citazioni
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
Social impact