Computational power of tissue P systems for generating control languages

摘要

Tissue P systems are a class of distributed and parallel models of computation inspired by the way of communication among living cells or between cells and their environment. In this work, we investigate the computational power of tissue P systems, where each rule is assigned either with a label chosen from an alphabet or with the empty label k. The sequence of labels of rules applied during a halting computation is defined as the result of the computation, and the set of all results computed by a given tissue P system is called a control language. We prove that tissue P systems with antiport rules of weight one and without symport rules characterize regular languages; tissue P systems with antiport rules of weight at most two (resp., symport rules of weight at most two) without symport rules (resp., antiport rules) are universal. Tissue P systems with antiport rules of weight one and symport rules of weight one are also proved to be universal. These results show that the rule complexity is crucial for tissue P systems to achieve a desired computational power.