Catalytic and Purely Catalytic P Systems and P Automata: Control Mechanisms for Obtaining Computational Completeness

• Autorzy: Freund R. , Oswald M. , Păun G.

Identyfikatory

DOI

10.3233/FI-2015-1144

• Języki publikacji: EN

Abstrakty

EN

The questions whether catalytic P systems with only one catalyst and purely catalytic P systems with only two catalysts can already be computationally complete in the generative case, still are open problems. For accepting P systems or P automata, the situation is even more complicated when we consider sets of vectors of natural numbers and not only sets of natural numbers – the number of catalysts increases with the dimension of the vectors. We here establish computational completeness for catalytic P systems and P automata with only one catalyst as well as for purely catalytic P systems and P automata with only two catalysts in the skin membrane by using specific variants of additional control mechanisms: in P systems and P automata with label selection, we only use rules from one set of a finite number of sets of rules in each computation step; in time-varying P systems and P automata the available sets of rules change periodically with time. The same control mechanisms also allow for computing partial recursive relations or functions of (vectors of) natural numbers when being used in catalytic P systems with one catalyst and purely catalytic P systems with two catalysts. Finally, these variants of P systems can also be used to generate or accept strings and to compute partial relations or functions on strings, and again we obtain computational completeness with only one catalyst in the case of catalytic P systems and two catalysts in the case of purely catalytic P systems.

Słowa kluczowe

EN

machine theory; information science; mathematical optimization; computational complexity; electronic data processing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 1/2
• Strony: 59--84
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Freund R.

• Faculty of Informatics, Vienna University of Technology Favoritenstr. 9, 1040 Vienna, Austria

autor

Oswald M.

• Faculty of Informatics, Vienna University of Technology Favoritenstr. 9, 1040 Vienna, Austria

autor

Păun G.

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

Bibliografia

• [1] Alhazov, A., Freund, R., Heikenwälder, H., Oswald, M., Rogozhin, Yu., Verlan, S.: Sequential P systems with regular control, in: Membrane Computing - 13th International Conference, CMC 2012, Budapest, Hungary, August 28-31, 2012, Revised Selected Papers (E. Csuhaj-Varjú, M. Gheorghe, G. Rozenberg, A. Salomaa, Gy. Vaszil, Eds.), vol. 7762 of Lecture Notes in Computer Science, Springer, Berlin, 2013, 112–127.
• [2] Csuhaj-Varjú, E., Vaszil, Gy.: P automata or purely communicating accepting P systems, in: Membrane Computing, International Workshop, WMC-CdeA 2002, Curtea de Arges¸, Romania, August 19-23, 2002, Revised Papers (Gh. Păun, G. Rozenberg, A. Salomaa, C. Zandron, Eds.), vol. 2597 of Lecture Notes in Computer Science, Springer, 2003, 219–233.
• [3] Dassow, J., Păun, Gh.: Regulated Rewriting in Formal Language Theory, vol. 18 of EATCS Monographs in Theoretical Computer Science, Springer, 1989.
• [4] Fernau, H., Freund, R., Oswald, M., Reinhardt, K.: Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars, Journal of Automata, Languages and Combinatorics, 12(1/2), 2007, 117–138.
• [5] Freund, R.: Purely catalytic P systems: two catalysts can be sufficient for computational completeness, in: CMC14 Proceedings – The 14th International Conference on Membrane Computing, Chişinău, August 20–23, 2013 (A. Alhazov, S. Cojocaru, M. Gheorghe, Yu. Rogozhin, Eds.), Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, 2013, 153–166.
• [6] Freund, R., Kari, L., Oswald, M., Sosík, P.: Computationally universal P systems without priorities: two catalysts are sufficient, Theoretical Computer Science, 330, 2005, 251–266.
• [7] Freund, R., Leporati, A., Maurid, G., Porreca, A. E., Verlan, S., Zandron, C.: Flattening in (Tissue) P Systems, in: Fourteenth Conference onMembrane Computing (CMC14) (A. Alhazov, S. Cojocaru,M. Gheorghe, Yu. Rogozhin, G. Rozenberg, A. Salomaa, Eds.), vol. 8340 of Lecture Notes in Computer Science, Springer, Berlin, 2014, 173–188.
• [8] Freund, R., Oswald, M.: A short note on analysing P systems, Bulletin of the EATCS, 78, 2002, 231–236.
• [9] Freund, R., Oswald, M.: Catalytic and purely catalytic P automata: control mechanisms for obtaining computational completeness, in: Fifth Workshop on Non-Classical Models of Automata and Applications (NCMA 2013) (S. Bensch, F. Drewes, R. Freund, F. Otto, Eds.), OCG, Wien, 2013, 133–150.
• [10] Freund, R., Păun, Gh.: 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 (T. Neary, M. Cook, Eds.), EPTCS 128, 2013, 47–61.
• [11] Freund, R., Păun, Gh.: Universal P systems: one catalyst can be sufficient, in: Proceedings 11th Brainstorming Week on Membrane Computing, Sevilla, 4–8 February 2013 (L. Valencia-Cabrera, M. García-Quismondo, L. F. Macas-Ramos, M. A. Martínez-del-Amor, Gh. Păun, A. Riscos-Núñez, Eds.), Fenix Editora, Sevilla, 2013, 81–96.
• [12] Krishna, S., Păun, A.: Results on catalytic and evolution-communication P systems, New Generation Computing, 22, 2004, 377–394.
• [13] Krithivasan, K., Păun, Gh., Ramanujan, A.: On controlled P systems, in: Proceedings 11th Brainstorming Week on Membrane Computing, Sevilla, 4–8 February 2013 (L. Valencia-Cabrera, M. García-Quismondo, L. F. Macas-Ramos, M. A. Martínez-del-Amor, Gh. Păun, A. Riscos- Núñez, Eds.), Fenix Editora, Sevilla, 2013, 137–152.
• [14] Minsky, M. L.: Computation: Finite and Infinite Machines, Prentice Hall, Englewood Cliffs, New Jersey, 1967.
• [15] Oswald, M.: P Automata, Dissertation, Vienna University of Technology, 2003.
• [16] Păun, Gh.: Computing with membranes, J. Comput. Syst. Sci., 61, 2003, 108–143.
• [17] Păun, Gh., Rozenberg, G., Salomaa, A., Eds.: The Oxford Handbook of Membrane Computing, Oxford University Press, 2010.
• [18] Rozenberg, G., Salomaa, A., Eds.: Handbook of Formal Languages, 3 volumes, Springer, 1997.
• [19] Sosík, P.,Matyšek, J.: Membrane computing: when communication is enough, in: Unconventional Models of Computation 2002 (C. Calude, M. Dinneen, F. Peper, Eds.), vol. 2509 of Lecture Notes in Computer Science, Springer, Berlin, 2002, 264–275.
• [20] The P Systems Website: http://ppage.psystems.eu.