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 P^C subseteq C, where P^C 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 Pi of P systems can be embedded into P systems simulating Turing machines, which exploit the elements of Pi 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.

Subroutines in P systems and closure properties of their complexity classes

Manzoni Luca;
2020-01-01

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 P^C subseteq C, where P^C 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 Pi of P systems can be embedded into P systems simulating Turing machines, which exploit the elements of Pi 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.
File in questo prodotto:
File Dimensione Formato  
Leporati.pdf

Open Access dal 05/07/2020

Tipologia: Bozza finale post-referaggio (post-print)
Licenza: Creative commons
Dimensione 380.77 kB
Formato Adobe PDF
380.77 kB Adobe PDF Visualizza/Apri
1-s2.0-S0304397518304201-main.pdf

Accesso chiuso

Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 546.15 kB
Formato Adobe PDF
546.15 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

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/11368/2947808
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact