Monodirectional Tissue P Systems With Promoters

Tissue P systems with promoters provide nondeterministic parallel bioinspired devices that evolve by the interchange of objects between regions, determined by the existence of some special objects called promoters. However, in cellular biology, the movement of molecules across a membrane is transported from high to low concentration. Inspired by this biological fact, in this article, an interesting type of tissue P systems, called monodirectional tissue P systems with promoters, where communication happens between two regions only in one direction, is considered. Results show that finite sets of numbers are produced by such P systems with one cell, using any length of symport rules or with any number of cells, using a maximal length 1 of symport rules, and working in the maximally parallel mode. Monodirectional tissue P systems are Turing universal with two cells, a maximal length 2, and at most one promoter for each symport rule, and working in the maximally parallel mode or with three cells, a maximal length 1, and at most one promoter for each symport rule, and working in the flat maximally parallel mode. We also prove that monodirectional tissue P systems with two cells, a maximal length 1, and at most one promoter for each symport rule (under certain restrictive conditions) working in the flat maximally parallel mode characterizes regular sets of natural numbers. Besides, the computational efficiency of monodirectional tissue P systems with promoters is analyzed when cell division rules are incorporated. Different uniform solutions to the Boolean satisfiability problem (SAT problem) are provided. These results show that with the restrictive condition of “monodirectionality,” monodirectional tissue P systems with promoters are still computationally powerful. With the powerful computational power, developing membrane algorithms for monodirectional tissue P systems with promoters is potentially exploitable.

I. Introduction

Bioinspired computing focuses on the designs and developments of computer algorithms and models based on biological mechanisms and living phenomena, which includes quantum computing [27]; DNA computing [33], [63], [67]; membrane computing [42]; etc. In this article, we focus on the research area of membrane computing, which is an active bioinspired field initiated by Păun [42], who discussed computing models motivated by the behavior and structure of cells, understanding the processes that take place in the compartments as computations. All the computing devices considered in this paradigm are called P systems [42]. Since the initial model proposes in this area, various system models have been presented and investigated in the aspects of computer science [1], [22], [52]; mathematics [7], [28]; and biochemistry [15], [23]. A brief summary of membrane computing can be found in monographs [43], [45], while a review of applications of this field can be found in [14] and [21].