Affiliations: Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, Academiei 5, MD-2028, Chişinău, Moldova. [email protected] | Faculty of Informatics, Vienna University of Technology, Favoritenstr. 9, 1040 Vienna, Austria. [email protected] | LACL, Université Paris Est – Créteil Val de Marne, 61, av. Général de Gaulle, 94010, Créteil, France. [email protected]
Note: [] Address for correspondence: Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, Academiei 5, MD-2028, Chişinău, Moldova
Abstract: 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.
