Dissemin is shutting down on January 1st, 2025

Published in

Elsevier, Information Sciences, (278), p. 285-297, 2014

DOI: 10.1016/j.ins.2014.03.053

Links

Tools

Export citation

Search in Google Scholar

Computational power of tissue P systems for generating control languages

Journal article published in 2014 by Xingyi Zhang, Yanjun Liu, Bin Luo, Linqiang Pan ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

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 A. 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.