In this paper, we consider recognizer P systems with antimatter and the influence of the matter/antimatter annihilation rules having weak priority over all the other rules or not. We first provide a uniform family of P systems with active membranes which solves the strongly NP-complete problem SAT, the Satisfiability Problem, without polarizations and without dissolution, yet with division for elementary membranes and with matter/antimatter annihilation rules having weak priority over all the other rules. Then we show that without this weak priority of the matter/antimatter annihilation rules over all the other rules we only obtain the complexity class P.

Diaz Pernil, D., Alhazov, A., Freund, R., Gutierrez Naranjo, M., Leporati, A. (2015). Recognizer P systems with antimatter. ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY, 18(3), 201-217.

Recognizer P systems with antimatter

ALHAZOV, ARTIOM
Secondo
;
LEPORATI, ALBERTO OTTAVIO
Ultimo
2015

Abstract

In this paper, we consider recognizer P systems with antimatter and the influence of the matter/antimatter annihilation rules having weak priority over all the other rules or not. We first provide a uniform family of P systems with active membranes which solves the strongly NP-complete problem SAT, the Satisfiability Problem, without polarizations and without dissolution, yet with division for elementary membranes and with matter/antimatter annihilation rules having weak priority over all the other rules. Then we show that without this weak priority of the matter/antimatter annihilation rules over all the other rules we only obtain the complexity class P.
Articolo in rivista - Articolo scientifico
Theoretical Computer Science; Membrane Computing; P systems
English
2015
18
3
201
217
none
Diaz Pernil, D., Alhazov, A., Freund, R., Gutierrez Naranjo, M., Leporati, A. (2015). Recognizer P systems with antimatter. ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY, 18(3), 201-217.
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/155726
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
Social impact