ROMJIST Volume 20, No. 1, 2017, pp. 42-56
Linqiang PAN, Yanfeng WANG, Suxia JIANG, Bosheng SONG Flat maximal parallelism in tissue P systems with promoters
ABSTRACT: Tissue P systems with promoters are distributed parallel computing models inspired by the structure of tissues and the way of communicating substances regulated by promoters. In this work, we consider tissue P systems with promoters working in a at maximally parallel way, where in each step, in each membrane, a maximal set of applicable rules is chosen and each rule in the set is applied exactly once. It is proved that tissue P systems with at most two promoters associated with any rule and using only symport rules of length 1 are Turing universal. Moreover, a uniform solution to the SAT problem is provided by tissue P systems with at most two promoters associated with any rule and using cell division rules and symport rules of length 1.KEYWORDS: Tissue P system, Promoter, Flat maximal parallelism, SAT problem, UniversalityRead full text (pdf)