Variants of P Colonies with Very Simple Cell Structure


  • Lucie Ciencialoví¡ Institute of Computer Science, Faculty of Philosophy and Science, Silesian University in Opava Bezruˇcovo ní¡m. 13, 74601 Opava, Czech Republic
  • Erzsébet Csuhaj-Varjú Computer and Automation Research Institute of the Hungarian Academy of Sciences Kende utca 13-17, 1111 Budapest, Hungary
  • Alica Kelemenoví¡ Department of Computer Science, Catholic University Ružomberok Ní¡m. A. Hlinku 56, 03401 Ružomberok, Slovakia
  • György Vaszil Computer and Automation Research Institute of the Hungarian Academy of Sciences Kende utca 13-17, 1111 Budapest, Hungary


P systems, colonies, P colonies, register machines


We study two very simple variants of P colonies: systems with only one object inside the cells, and systems with insertion-deletion programs, so called P colonies with senders and consumers. We show that both of these extremely simple types of systems are able to compute any recursively enumerable set of vectors of non-negative integers.


L. Cienciala, L. Ciencialová, A. Kelemenová. On the number of agents in P colonies. In: Membrane Computing. 8th International Workshop, WMC 2007. Thessaloniki, Greece, June 25-28, 2007. Re- vised Selected and Invited Papers. Edited by G. Eleftherakis, P. Kefalas, Gh. P˘aun, G. Rozenberg, A. Salomaa. Volume 4860 of Lecture Notes in Computer Science, Springer-Verlag, Berlin-Heidelberg, 2007, 193-208.

E. Csuhaj-Varjú, J. Dassow, J. Kelemen, Gh. P˘aun. Grammar Systems - A Grammatical Approach to Distribution and Cooperation. Gordon and Breach, London, 1994.

E. Csuhaj-Varjú, J. Kelemen, A. Kelemenová, Gh. P˘aun, Gy. Vaszil. Computing with cells in envi- ronment: P colonies. Journal of Multi-Valued Logic and Soft Computing 12:201-215, 2006.

J. Kelemen, A. Kelemenová. A grammar-theoretic treatment of multi-agent systems. Cybernetics and Systems 23:621-633, 1992.

J. Kelemen, A. Kelemenová, Gh. P˘aun. Preview of P colonies: A biochemically inspired computing model. In: Workshop and Tutorial Proceedings. Ninth International Conference on the Simulation and Synthesis of Living Systems (Alife IX). Edited by M. Bedau et al. Boston Mass., 2004, 82-86.

M. Minsky. Computation - Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967.

Gh. Păun. Membrane Computing - An Introduction. Springer-Verlag, Berlin, 2002.



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.