201. Cell-like P systems with polarizations and minimal rules
- Author
-
Bosheng Song, David Orellana-Martín, Linqiang Pan, Mario J. Pérez-Jiménez, Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial, Universidad de Sevilla. TIC193: Computación Natural, and Ministerio de Economia, Industria y Competitividad (MINECO). España
- Subjects
Discrete mathematics ,Class (set theory) ,General Computer Science ,Computer science ,Computation ,0102 computer and information sciences ,02 engineering and technology ,Divisibility rule ,Membrane Computing ,Minimal rule ,Object (computer science) ,01 natural sciences ,Universality ,PSPACE ,Theoretical Computer Science ,Turing machine ,symbols.namesake ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,symbols ,020201 artificial intelligence & image processing ,Bio-inspired computing ,Time complexity ,Membrane computing - Abstract
P systems with active membranes are a class of computation models in the area ofmembrane computing, which are inspired from the mechanism by which chemicalsinteract and cross cell membranes. In this work, we consider a normal form of P systemswith active membranes, called cell-like P systems with polarizations and minimal rules,where rules are minimal in the sense that an object evolves to exactly one object withthe application of an evolution rule or a communication rule, or an object evolves to twoobjects that are assigned to the two new generated membranes by applying a division rule.The present work investigates the computational power of P systems with polarizationsand minimal rules. Specifically, results about Turing universality and non-universality areobtained with the combination of the number of membranes, the number of polarizations,and the types of rules. We also show that polarizationless P systems with minimal rules areequivalent to Turing machines working in a polynomial space, that is, the class of problemsthat can be solved in polynomial time by polarizationless P systems with minimal rules isequal to the classPSPACE. Ministerio de Economía, Industria y Competitividad TIN2017-89842-P (MABICAP)
- Published
- 2020