2021-04-282021-04-282020Pan, L., Orellana Martín, D., Song, B. y Pérez Jiménez, M.d.J. (2020). Cell-like P systems with polarizations and minimal rules. Theoretical Computer Science, 816 (May 2020)0304-3975https://hdl.handle.net/11441/108029P 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.application/pdf18engAttribution-NonCommercial-NoDerivatives 4.0 Internacionalhttp://creativecommons.org/licenses/by-nc-nd/4.0/Bio-inspired computingMembrane ComputingMinimal ruleUniversalityPSPACEinfo:eu-repo/semantics/articleinfo:eu-repo/semantics/openAccess10.1016/j.tcs.2019.10.00121876759