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 derivation mode, where, if possible, one rule is applied in a derivation step, and the set maximally parallel derivation mode, where in each derivation step a non-extendable set of rules indicating the same target cell is applied. With the set maximally parallel derivation 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 — only the three polarizations $- 1$ , $0$ , $1$ are sufficient — allows for obtaining computational completeness even for tissue P systems working in the sequential mode.

This paper is an extended and improved version of the paper presented at AFL 2017 in Debrecen.

Communicated by Erzsébet Csuhaj-Varjú, Pál Dömösi, and György Vaszil

Keywords:

References

1. A. Alhazov, R. Freund, V. Rogozhin and Yu. Rogozhin, Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors, Natural Computing 15(1) (2016) 51–68. Crossref, Web of Science, Google Scholar
2. A. Alhazov, R. Freund and S. Verlan, P systems working in maximal variants of the set derivation mode, Membrane Computing — 17th International Conference, CMC 2016, Milan, Italy, July 25–29, 2016, Revised Selected Papers, eds. A. Leporati, G. Rozenberg, A. Salomaa and C. Zandron, Lecture Notes in Computer Science, Vol. 10105 (2016), pp. 83–102. Google Scholar
3. F. Arroyo, S. Canaval, V. Mitrana and Ş. Popescu, On the computational power of networks of polarized evolutionary processors, Information and Computation 253(3) (2017) 371–380. Crossref, Web of Science, Google Scholar
4. F. Arroyo, S. G. Canaval, V. Mitrana and Ş. Popescu, Networks of polarized evolutionary processors are computationally complete, International Conference on Language and Automata Theory and Applications. LATA 2014, eds. A. Dediu, C. Martín-Vide, J. Sierra-Rodríguez and B. Truthe, Lecture Notes in Computer Science, Vol. 8370 (Springer, 2014), pp. 101–112. Crossref, Google Scholar
5. J. Castellanos, C. Martín-Vide, V. Mitrana and J. M. Sempere, Networks of evolutionary processors, Acta Informatica 39(6–7) (2003) 517–529. Crossref, Web of Science, Google Scholar
6. J. Dassow and Gh. Păun, Regulated Rewriting in Formal Language Theory (Springer, 1989). Crossref, Google Scholar
7. J. Dassow and Gh. Păun, On the power of membrane computing, J. UCS 5(2) (1999) 33–49. Google Scholar
8. R. Freund, O. Ibarra, Gh. Păun and H.-C. Yen, Matrix languages, register machines, vector addition systems, Third Brainstorming Week on Membrane Computing, eds. M. A. G. Naranjo, A. Riscos-Núñez, F. J. Romero-Campero and D. Sburlan (Fénix Editora, Sevilla, España, 2005), pp. 155–167. Google Scholar
9. R. Freund, M. Kogler, Yu. Rogozhin and S. Verlan, Graph-controlled insertion-deletion systems, Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems, DCFS 2010, Saskatoon, Canada, 8–10th August 2010, eds. I. McQuillan and G. Pighizzini, EPTCS, Vol. 31 (2010), pp. 88–98. Crossref, Google Scholar
10. R. Freund and M. Oswald, Tissue P systems and (mem)brane systems with mate and drip operations working on strings, Electr. Notes Theor. Comput. Sci. 171(2) (2007) 105–115. Crossref, Google Scholar
11. R. Freund and Gh. Păun, How to obtain computational completeness in P systems with one catalyst, Proceedings Machines, Computations and Universality 2013, MCU 2013, Zürich, Switzerland, September 9–11, 2013, eds. T. Neary and M. Cook, EPTCS, Vol. 128 (2013), pp. 47–61. Crossref, Google Scholar
12. R. Freund, V. Rogojin and S. Verlan, Computational completeness of networks of evolutionary processors with elementary polarizations and a small number of processors, Descriptional Complexity of Formal Systems — 19th IFIP WG 1.02 International Conference, DCFS 2017, Milano, Italy, July 3–5, 2017, Proceedings, eds. G. Pighizzini and C. Câmpeanu, Lecture Notes in Computer Science, Vol. 10316 (Springer, 2017), pp. 140–151. Crossref, Google Scholar
13. R. Freund, Yu. Rogozhin and S. Verlan, Generating and accepting P systems with minimal left and right insertion and deletion, Natural Computing 13(2) (2014) 257–268. Crossref, Web of Science, Google Scholar
14. C. Martín-Vide, J. Pazos, Gh. Păun and A. Rodríguez-Patón, A new class of symbolic abstract neural nets: Tissue P systems, Computing and Combinatorics. COCOON 2002, eds. O. Ibarra and L. Zhang, Lecture Notes in Computer Science, Vol. 2387 (Springer, 2002), pp. 290–299. Crossref, Google Scholar
15. M. L. Minsky, Computation. Finite and Infinite Machines (Prentice Hall, Englewood Cliffs, NJ, 1967). Google Scholar
16. Ş. Popescu, Networks of polarized evolutionary processors with elementary polarization of symbols, Proceedings NCMA 2016 (OCG, 2016), pp. 275–285. Google Scholar
17. Gh. Păun, Computing with membranes, J. Comput. Syst. Sci. 61(1) (2000) 108–143. Crossref, Web of Science, Google Scholar
18. Gh. Păun, G. Rozenberg and A. Salomaa (eds.), The Oxford Handbook of Membrane Computing (Oxford University Press, Oxford, England, 2010). Crossref, Google Scholar
19. G. Rozenberg and A. Salomaa (eds.), Handbook of Formal Languages (Springer, 1997). Crossref, Google Scholar
20. Bulletin of the International Membrane Computing Society (IMCS), http://membranecomputing.net/IMCSBulletin/index.php. Google Scholar
21. The P Systems Website, http://ppage.psystems.eu/. Google Scholar