Length P Systems

• Autorzy: Alhazov A. , Freund R. , Ivanov S.

Identyfikatory

DOI

10.3233/FI-2014-1088

• Języki publikacji: EN

Abstrakty

EN

In this paper, we examine P systems with a linear membrane structure, i.e., P systems in which only one membrane is elementary and the output of which is read out as the sequence of membrane labels in the halting configuration or vectors/numbers represented by this sequence. We investigate the computational power of such systems, depending on the number of membrane labels, kinds of rules used, and some other possible restrictions. We prove that two labels, elementary membrane creation and dissolution, together with the usual send-in and send-out rules, suffice to achieve computational completeness, even with the restriction that only one object is allowed to be present in any configuration of the system. On the other hand, limiting the number of labels to one reduces the computational power to the regular sets of non-negative integers. We also consider other possible variants of such P systems, e.g., P systems in which all membranes but one have the same label, P systems with membrane duplication rules, or systems in which multiple objects are allowed to be present in a configuration, and we describe the computational power of all these models.

Słowa kluczowe

EN

computational complexity; linear systems; configurations; completeness theorem; biological membranes

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 134, nr 1/2
• Strony: 17--37
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Alhazov A.

• Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, Academiei 5, MD-2028, Chişinău, Moldova

autor

Freund R.

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

autor

Ivanov S.

• LACL, Université Paris Est – Créteil Val de Marne 61, av. Général de Gaulle, 94010, Créteil, France

Bibliografia

• [1] Alhazov, A.: P Systems without Multiplicities of Symbol-Objects, Information Processing Letters 100 (3), 2006, 124–129.
• [2] Alhazov, A., Freund, R., Ivanov, S: Length P Systems with a Lone Traveler, Proceedings of the 12th Brainstorming Week on Membrane Computing, 2014, 37–46.
• [3] Alhazov, A., Freund, R., Ivanov, S: Length P Systems with a Lonesome Traveler, 15th International Conference on Membrane Computing, CMC15, 2014.
• [4] Alhazov, A., Freund, R., Riscos-Núñez, A.: Membrane Division, Restricted Membrane Creation and Object Complexity in P Systems, International Journal of Computer Mathematics 83 (7), 2006, 529-548.
• [5] Bernardini, F., Gheorghe, M.: Languages Generated by P Systems with Active Membranes, New Generation Computing 22 (4), 2004, 311–329.
• [6] Freund, R.: Special Variants of P Systems Inducing an Infinite Hierarchy with Respect to the Number of Membranes, Bulletin of the EATCS 75, 2001, 209–219.
• [7] Freund, R., Ibarra, O.H., Păun, Gh., Yen, H.C.: Matrix Languages, Register Machines, Vector Addition Systems, Proceedings of the Third Brainstorming Week on Membrane Computing, Sevilla, 2005, 155–167.
• [8] M. L. Minsky: Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, New Jersey, USA, 1967.
• [9] Gh. Păun: Membrane Computing. An Introduction. Springer, 2002.
• [10] Gh. Păun, G. Rozenberg, A. Salomaa (Eds.): The Oxford Handbook of Membrane Computing. Oxford University Press, 2010.
• [11] G. Rozenberg, A. Salomaa (Eds.): Handbook of Formal Languages, 3 volumes. Springer, 1997.
• [12] The P Systems Website: http://ppage.psystems.eu/.