Recognizer P systems with antimatter
Închide
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
142 0
SM ISO690:2012
DIAZ-PERNIL, Daniel, ALHAZOV, Artiom, FREUND, Rudolf, GUTIERREZ-NARANJO, Miguel A., LEPORATI, Alberto. Recognizer P systems with antimatter. In: Romanian Journal of Information Science and Technology, 2015, vol. 18, pp. 201-217. ISSN 1453-8245.
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Romanian Journal of Information Science and Technology
Volumul 18 / 2015 / ISSN 1453-8245

Recognizer P systems with antimatter


Pag. 201-217

Diaz-Pernil Daniel1, Alhazov Artiom2, Freund Rudolf3, Gutierrez-Naranjo Miguel A.1, Leporati Alberto4
 
1 University of Sevilla,
2 Institute of Mathematics and Computer Science ASM,
3 Faculty of Informatics, TU Wien,
4 University of Milano-Bicocca
 
 
Disponibil în IBN: 2 octombrie 2023


Rezumat

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.

Cuvinte-cheie
P systems, Membrane computing, Spiking