Flip-Flop P Systems With Proteins on Membranes in a Time-Free Manner

Abstract

Flip-flop P systems with proteins are a bio-inspired variant of cell-like P systems in membrane computing, where proteins can control the execution of rules. In this work, firstly, in order to simulate the fact that the execution time of biochemical reactions is uncertain, considering time-freeness, we therefore construct a novel variant, namely timed flip-flop P systems with proteins, where the protein on each membrane only has two types of working states, and such a system runs under the time-freeness mode; secondly, we study the computation power of this variant, and it is shown that a system with only one membrane and a maximum rule length of 4 is Turing universal; moreover, based on the variant, a solution to the $\mathcal {SAT}$ problem is obtained by the constructed system in polynomial time. Our work indicates that the constructed variant with time-freeness can still solve the $\mathcal {SAT} $ problem in feasible time. Because time-freeness of rules is employed, the variant may be more suitable for particular applications.

Keywords

• P system
• protein
• university
• SAT
• time-freeness