(Tissue) P Systems with Vesicles of Multisets

Artiom Alhazov
(Institute of Mathematics and Computer Science, Academy of Sciences of Moldova)
Rudolf Freund
(Faculty of Informatics, TU Wien)
Sergiu Ivanov
(TIMC-IMAG/DyCTiM, Faculty of Medicine of Grenoble)
Sergey Verlan
(Laboratoire d'Algorithmique, Complexité et Logique, Université Paris Est Créteil)

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.

In Erzsébet Csuhaj-Varjú, Pál Dömösi and György Vaszil: Proceedings 15th International Conference on Automata and Formal Languages (AFL 2017), Debrecen, Hungary, September 4-6, 2017, Electronic Proceedings in Theoretical Computer Science 252, pp. 11–25.
Published: 21st August 2017.

ArXived at: https://dx.doi.org/10.4204/EPTCS.252.6 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org