Search

Cell-like P systems with channel states, which are a variant of tissue P systems in membrane computing, can be viewed as highly parallel computing devices based on the nested structure of cells, where communication rules are classified as symport rules and antiport rules. In this work, we remove the antiport rules and construct a novel variant, namely, cell-like P systems with channel states and symport rules, where one rule is only allowed to be nondeterministically applied once per channel. To explore the computational efficiency of the variant, we solve the S A T problem and obtain a uniform solution in polynomial time with the maximal length of rules 1. The results of our work are reflected in the following two aspects: first, communication rules are restricted to only one type, namely, symport rules; second, the maximal length of rules is decreased from 2 to 1. Our work indicates that the constructed variant with fewer rule types can still solve the S A T problem and obtain better results in terms of computational complexity. Hence, in terms of computational efficiency, our work is a notable improvement. [ABSTRACT FROM AUTHOR]

Tissue P systems provide distributed parallel devices inspired by actual biological reality, where communication rules are used for object exchange between cells (or between cells and the environment). In such systems, the environment continuously provides energy to cells, so the cells are very dependent on the objects in the environment. In biology, there is a mechanism called homeostasis, that is, an internal organism is independent from the external conditions, thus keeping itself relatively stable. Inspired by this biological fact, in this paper, we assume that the environment no longer provides energy for cells, introducing multiset rewriting rules into tissue P systems, thereby constructing a novel computational model called homeostasis tissue-like P systems. Based on the model, we construct two uniform solutions in feasible time. One solution is constructed to solve the 3-coloring problem in linear time in standard time, and the other solution is constructed to solve the $\mathcal {SAT} $ problem with communication rules and multiset rewriting rules of the length at most 3 in time-free mode. Moreover, we prove that the constructed system can generate any Turing computable set of numbers using communication rules and multiset rewriting rules with a maximal length 3, working in the mode of standard time and time-free, respectively. The results show that our constructed system does not rely on the environment and reflects the phenomenon of biological homeostasis. In addition, although the system runs in time-free way, it not only has Turing university, but also can effectively solve NP-complete problem. [ABSTRACT FROM AUTHOR]

P systems with active membranes are a class of bioinspired computing models, where the rules are used in the non-deterministic maximally parallel manner. In this paper, first, a new variant of timed P systems with active membranes is proposed, where the application of rules can be regulated by promoters with only two polarizations. Next, we prove that any Turing computable set of numbers can be generated by such a P system in the time-free way. Moreover, we construct a uniform solution to the $\mathcal{SAT}$ problem in the framework of such recognizer timed P systems in polynomial time, and the feasibility and effectiveness of the proposed system is demonstrated by an instance. Compared with the existing methods, the P systems constructed in our work require fewer necessary resources and RS-steps, which show that the solution is effective to NP -complete problem. [ABSTRACT FROM AUTHOR]

Tissue P systems are a class of computing models inspired by intercellular communication, where the rules are used in the nondeterministic maximally parallel manner. As we know, the execution time of each rule is the same in the system. However, the execution time of biochemical reactions is hard to control from a biochemical point of view. In this work, we construct a uniform and efficient solution to the SAT problem with tissue P systems in a time-free way for the first time. With the P systems constructed from the sizes of instances, the execution time of the rules has no influence on the computation results. As a result, we prove that such system is shown to be highly effective for NP-complete problem even in a time-free manner with communication rules of length at most 3. [ABSTRACT FROM AUTHOR]