2017/08/22 by Artiom Alhazov, Rudolf Freund, Sergiu Ivanov +1
Computer Science · #cs.FL
paper · pdf · doi:10.4204/eptcs.252.6
published as EPTCS 252, 2017, pp. 11-25 · In Proceedings AFL 2017, arXiv:1708.06226
arxiv created 2017/08/22 · arxiv updated 2017/08/23
We consider tissue P systems working on vesicles of multisets with the very simple operations of insertion, deletion, and substitution of single objects. With the whole multiset being enclosed in a vesicle, sending it to a target cell can be indicated in those simple rules working on the multiset. As derivation modes we consider the sequential mode, where exactly one rule is applied in a derivation step, and the set maximal mode, where in each derivation step a non-extendable set of rules is applied. With the set maximal mode, computational completeness can already be obtained with tissue P systems having a tree structure, whereas tissue P systems even with an arbitrary communication structure are not computationally complete when working in the sequential mode. Adding polarizations (-1, 0, 1 are sufficient) allows for obtaining computational completeness even for tissue P systems working in the sequential mode.