Article
Recognizer P Systems with Antimatter
Author/s | Díaz Pernil, Daniel
Alhazov, Artiom Freund, Rudolf Gutiérrez Naranjo, Miguel Ángel Leporati, Alberto |
Department | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Publication Date | 2015 |
Deposit Date | 2021-04-07 |
Published in |
|
Abstract | In this paper, we consider recognizer P systems with antimatter
and the in
uence of the matter/antimatter annihilation rules having weak
priority over all the other rules or not. We rst provide a uniform family of ... In this paper, we consider recognizer P systems with antimatter and the in uence of the matter/antimatter annihilation rules having weak priority over all the other rules or not. We rst provide a uniform family of P systems with active membranes which solves the strongly NP-complete problem SAT, the Satis ability 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 |
Funding agencies | Ministerio de Economía y Competitividad (MINECO). España |
Project ID. | TIN2012-37434 |
Citation | Díaz Pernil, D., Alhazov, A., Freund, R., Gutiérrez Naranjo, M.Á. y Leporati, A. (2015). Recognizer P Systems with Antimatter. Romanian Journal of Information Science and Technology (ROMJIST), 18 (3), 201-217. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Recognizer P systems with ... | 149.9Kb | [PDF] | View/ | |