P-Systems are abstract machines inspired to the behaviour of cells which we can see like simple biological processing units. Many types of P-Systems have been developed considering different aspects of the cells working principles, obtaining different computational models. In this paper we introduce Active P-Colonies (APC), a variant of the model P-Colony systems. P-Colony systems are a model of computation based on the collaboration among different agents placed in a shared passive environment (i.e. a space where no computing operations take place). First of all, we show that using the P-Colony system basic model it is not possible to solve problems in the computational class NP (unless P=NP). Inspired by what has been done for the basic variant of P-Systems, we extend the original model by including new types of rules and new biological behaviours like duplication and membrane dissolution. In fact, in APC the agents are able to duplicate themselves obtaining new processing units having the same computational power as the original unit. The cells can also dissolve their membrane, releasing the contents into the environment. The obtained systems are able to solve in polynomial time (and exponential space) computationally hard problems. In particular, we focus on the development of systems able to solve problems in the classes NP (SAT), coNP (UNSAT) and #P (#SAT).

Scarpone, M., Molteni, G., Leporati, A., & Zandron, C. (2022). Active P-Colonies. INFORMATION SCIENCES, 587(March 2022), 642-653 [10.1016/j.ins.2021.12.052].

Active P-Colonies

Leporati A.
Penultimo
;
Zandron C.
Ultimo
2022

Abstract

P-Systems are abstract machines inspired to the behaviour of cells which we can see like simple biological processing units. Many types of P-Systems have been developed considering different aspects of the cells working principles, obtaining different computational models. In this paper we introduce Active P-Colonies (APC), a variant of the model P-Colony systems. P-Colony systems are a model of computation based on the collaboration among different agents placed in a shared passive environment (i.e. a space where no computing operations take place). First of all, we show that using the P-Colony system basic model it is not possible to solve problems in the computational class NP (unless P=NP). Inspired by what has been done for the basic variant of P-Systems, we extend the original model by including new types of rules and new biological behaviours like duplication and membrane dissolution. In fact, in APC the agents are able to duplicate themselves obtaining new processing units having the same computational power as the original unit. The cells can also dissolve their membrane, releasing the contents into the environment. The obtained systems are able to solve in polynomial time (and exponential space) computationally hard problems. In particular, we focus on the development of systems able to solve problems in the classes NP (SAT), coNP (UNSAT) and #P (#SAT).
Articolo in rivista - Articolo scientifico
Computing efficiency; Membrane computing; P-Colonies; P-Systems;
English
642
653
12
Scarpone, M., Molteni, G., Leporati, A., & Zandron, C. (2022). Active P-Colonies. INFORMATION SCIENCES, 587(March 2022), 642-653 [10.1016/j.ins.2021.12.052].
Scarpone, M; Molteni, G; Leporati, A; Zandron, C
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/344576
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
Social impact