Membrane computing is inspired by biological living cells. As an essential category of membrane computing, conventional tissue-like P systems do not have polarizations on cells. Nevertheless, polarizations may exist in actual biological tissues. Inspired by the biological phenomenon, the novel variant tissue-like P systems with polarizations is proposed, in which the execution of rules may be influenced by polarizations on cells.
To construct a variant with more excellent computational properties, a research team led by Yueguo LUO published their new research on 15 August 2024 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
Currently, the computational power of conventional tissue-like P systems with a rule length of at most 2 is restricted. The team proposed the novel variant to obtain the same computational power as a Turing machine, where the maximum lengths of symport rules and antiport rules are 2 and 4, respectively, or the maximum length of symport rules is 4 (if only this type of rule is used). In both cases, only one cell and three types of polarizations are employed.
Cell division rules with polarizations are introduced to solve the classical SAT problem, passing from non-efficiency to efficiency, by combining antiport rules and symport rules, due to cell division rules, tissue-like P systems with polarizations can solve the SAT problem in polynomial time, where the maximum rule length is 4.
These results show that the variant can be employed as a distributed parallel computing paradigm. In particular, it is theoretically feasible to apply this variant in some specific applications that require precise rule control.
DOI: 10.1007/s11704-024-3154-9