Symport/Antiport P Systems with Three Objects Are Universal

• Autorzy: Păun G. , Pérez-Jiménez M. J. , Pazos J. , Rodriguez-Patón A.
• Języki publikacji: EN

Abstrakty

EN

The operations of symport and antiport, directly inspired from biology, are already known to be rather powerful when used in the framework of P systems. In this paper we confirm this observation with a quite surprising result: P systems with symport/antiport rules using only three objects can simulate any counter machine, while systems with only two objects can simulate any blind counter machine. In the first case, the universality (of generating sets of numbers) is obtained also for a small number of membranes, four.

Słowa kluczowe

EN

membrane computing; turing computability; register machine; symport/antiport

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 353--367
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Păun G.

• Institute of Mathematics of the Romanian Academy, PO Box 1 - 764, 70700 Bucuresti, Romania

autor

Pérez-Jiménez M. J.

• Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain

autor

Pazos J.

• Department of Artificial Intelligence, Faculty of Computer Science Polytechnical University of Madrid, Campus de Montegancedo Boadilla del Monte 28660, Madrid, Spain

autor

Rodriguez-Patón A.

• Department of Artificial Intelligence, Faculty of Computer Science Polytechnical University of Madrid, Campus de Montegancedo Boadilla del Monte 28660, Madrid, Spain

Bibliografia

• [1] B. Alberts, A. Johnson, J. Lewis, M. Raff, K. Roberts, P. Walter, Molecular Biology of the Cell, 4th ed. Garland Science, New York, 2002.
• [2] A. Alhazov, M. Margenstern, V. Rogozhin, Y. Rogozhin, S. Verlan, Communicative P systems with minimal cooperation. In G. Mauri, Gh. Păun, M.J. Pérez-Jiménez, G. Rozenberg, A. Salomaa, eds., Membrane Computing. International Workshop WMC5, Milan, Italy, 2004. Revised Papers, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2005 (to appear).
• [3] R. Freund, A. Păun, Membrane systems with symport/antiport rules: universality results. In Gh. Păun, G. Rozenberg, A. Salomaa, C. Zandron, eds., Membrane Computing. International Workshop, WMC 2002, Curtea de Arges¸, Romania. Revised Papers, Lecture Notes in Computer Science, 2597, Springer-Verlag, Berlin, 2002, 270–287.
• [4] R. Freund, Gh. Păun,M.J. Pérez-Jiménez, Tissue-like P systems with channel-states. Brainstorming Week on Membrane Computing, Sevilla, February 2004, TR 01/04 of Research Group on Natural Computing, Sevilla University, 2004, 206–223, and Theoretical Computer Science, 2004, in press.
• [5] S.A. Greibach, Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science, 7 (1978), 311–324.
• [6] C. Martín-Vide, Gh. Păun, J. Pazos, A. Rodríguez-Patón, Tissue P systems. Theoretical Computer Science, 296, 2 (2003), 295–326.
• [7] M. Minsky, Computation – Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967.
• [8] A. Păun, Gh. Păun, The power of communication: P systems with symport/antiport. New Generation Computing, 20, 3 (2002), 295–306.
• [9] Gh. Păun, Computing with Membranes – An Introduction. Springer-Verlag, Berlin, 2002.
• [10] Y. Rogozhin, Small universal Turing machines. Theoretical Computer Science, 168 (1996), 215–240.
• [11] P. Sosik, J. Matysek, Membrane computing: when communication is enough. In C.S. Calude, M.J. Dinneen, F. Peper, eds., Unconventional Models of Computation 2002, Lecture Notes in Computer Science, 2509 Springer-Verlag, Berlin, 2002, 264–275.
• [12] G. Vaszil, On the size of P systems with minimal symport/antiport. Pre-Proceedings of Workshop on Membrane Computing, WMC5, Milano, Italy, June 2004, 422–431