On Catalytic P Systems with One Catalyst

On Catalytic P Systems with One Catalyst Drago¸s Sburlan Faculty of Mathematics and Informatics Ovidius University of Constanta, Romania [email protected] Summary. In this paper we address the possibility of studying the computational capabilities of catalytic P systems with one catalyst by the means of iterated finite state transducers. We also give a normal form for catalytic P systems. 1 Introduction P systems are a computational model introduced by G. P˘aun in [4]. One of the basic variant considered there was P systems with catalysts and priorities; these systems where shown to be computationally universal. In [2], Sos´ık and Freund proved that priorities among the rules can be discarded from the model without any loss of computational power. Moreover, it was shown that for extended P systems only one membrane and two catalysts are enough for reaching computational universality. However, the computational power for P systems with only one catalyst was not established. The present paper characterize these systems in terms of iterated finite state transducers hence it converts an open problem from P system framework to an open problem from string rewriting theory. Additionally, a normal form for catalytic P systems is presented. 2 Preliminaries We assume the reader is acquainted with the basic notions and notations from the formal language theory (see [3] for more details). Here we only recall the definitions and the results which are useful for the present work. If FL is a family of languages, then NFL denotes the family of length sets of languages in FL. We denote by REG,CF,REC, and RE the family of regular, context-free, recursive, and recursively enumerable languages, respectively. It is known that NREG =NCF (NREC (NRE. 284 D. Sburlan 2.1 Iterated Finite State Transducers An iterated (finite state) sequential transducer (IFT) is a construct γ= (K, V, q0, a0, F, P ), where Kis a finite set of states,Vis a finite set of symbols (the alphabet of γ), K∩V=∅,q0∈Kis the initial state,a0∈Vis the starting symbol,F⊆Kis the set of final states, and Pis a finite set of transition rules of the form qa →xp, for q, p ∈K,a∈V, and x∈V∗. For q, p ∈Kand u, v, x ∈V∗,a∈V, a direct transition step of γis defined as uqav `uxpv if and only if qa →xp ∈P. The reflexive and transitive closure of the relation `is denoted by `∗. In general, for α, β ∈V∗we say that αderives into βand we write α=⇒β, if and only if q0α`∗βp for some p∈K. By =⇒∗we denote the reflexive transitive closure of =⇒. If q0α`∗βp such that p∈F, then we write α=⇒fβ. The language generated by γis L(γ) = {β∈V|a0=⇒∗α=⇒f β, for some α∈V∗}. If for each pair (q, a)∈K×V, there is at most one transition rule qa `xp ∈P, then γis called deterministic (otherwise, it is called nondeterministic). The family of languages generated by nondeterministic IFTs with at most n≥1 states is denoted by IF Tn. It is known from [1] that CF ⊂IF T2⊆IF T3⊆IFT4=RE. Moreover, there are non-semilinear languages belonging to IF T2, and there are non-recursive languages belonging to IF T3. Consequently, if we denote by NIFTn, n≥1, the family of length sets of languages from IF Tn, then we have that NREG =NCF (NIF T2⊆NIFT3⊆NIF T4=NRE. 2.2 Membrane Systems Acatalytic P system of degree m≥1 is a construct Π= (O, C, µ, w1, . . . , wm, R1, . . . , Rm, i0) where •Ois an alphabet of objects; •C⊆Ois the set of catalysts; •µis a hierarchical tree structure of m≥1 uniquely labelled membranes (which delimit the regions of Π); typically, the set of labels is {1, . . . , m}; •wi∈O∗, for 1 ≤i≤m, are the multisets of objects initially present in the mregions of µ; •Ri, 1 ≤i≤m, are finite sets of evolution rules; these rules can be noncooperative a→vor catalytic ca →cv, where a∈O\C,v∈((O\C)× {here, out, in})∗, and c∈C; •i0∈ {1, . . . , m}is the label of the output region of Π. Aconfiguration of Πis a vector C= (α1, . . . , αm), where αi∈O∗, 1 ≤i≤m, is a multiset of objects present in the region iof Π. The vector C0= (w1, . . . , wm) is the initial configuration of Π. Starting from the initial configuration and always applying in all membranes a maximal multiset of evolution rules in parallel, one On Catalytic P Systems with One Catalyst 285 gets a sequence of consecutive configurations. By ⇒is denoted the transition between two consecutive configurations. A sequence (finite or infinite) of transitions starting from C0represents a computation of Π. A computation of Πis a halting one if no rules can be applied to the last configuration (the halting configuration). The result of a halting computation is the number of objects from Ocontained in the output region i0, in the halting configuration. A non-halting computation yields no result. By collecting the results of all possible halting computations of a given P system Π, one gets N(Π) – the set of all natural numbers generated by Π. The family of all sets of numbers computed by catalytic P systems with at most m membranes and kcatalysts is denoted by NOPm(catk). The above definition can be relaxed such that in a halting configuration one counts only the symbols from a given alphabet Σ⊆O. In particular, one can consider Σ=O\C; correspondingly, the family of all sets of numbers computed by such particular P systems will be denoted by NO−CPm(catk). It is known (see [7], for instance) that NO−CPm(catk) = NO−CP1(catk). Moreover, in [2] it is shown that NO−CP1(cat2) = NRE. 3 A Normal Form for P Systems with Catalysts The following result states that any catalytic P system is equivalent with a catalytic P system having a restriction on the form of the rules. Theorem 1. For any P system Πwith catalysts there exists an equivalent P system Πwith one region and whose rules are of the form a→α, with |α| ≤ 2, or ca →cβ, with |β| ≤ 1. Proof. As we already stated in Section 2.2, for any P system with catalysts and n > 1 membranes one can construct an equivalent P system with the same number of catalysts and one membrane. Consequently, without loss of generality, we might assume that Πhas only one membrane, that is Π= (O, C, [ ]1, w1, R1, i0). Let O\C={a1, a2, . . . , ap}and let m=max{|α| | a→α∈R1or ca →cα ∈ R1}. In addition, assume for our convenience that the rules of Πare labeled in an unique manner with numbers from the set {1, . . . , card(R1)}. Then one can construct an equivalent P system Π= (O, C, [ ]1, w1, R1, i0) where O=O∪ {a(i,j)|1≤i≤p, 1≤j≤m} ∪ {X(i,j)|i:a→αi∈R1,1≤j≤m−2}. The set R1is defined as follows (for the simplicity of the explanations, we will only consider the rules in R1that are useful for simulating a non-cooperative rule from R1; the rules corresponding to a catalytic rule are defined similarly, therefore we will not present them here). Let i:a→aj1aj2. . . ajk∈R1and let m−k=t. Then we add to R1the rules: 286 D. Sburlan a→X(i,1) (1) X(i,1) →X(i,2) ... X(i,t−1) →X(i,t) X(i,t)→a(j1,k−1)X(i,t+1) (2) X(i,t+1) →a(j2,k−2)X(i,t+2) . . . X(i,t+k−3) →a(jk−2,2)X(i,t+k−2) X(i,t+k−2) →a(jk−1,1)a(jk,1) a(i,m)→a(i,m−1) (3) a(i,m−1) →a(i,m−2) ... a(i,1) →ai The proof is based on the existence of the universal global clock that governs the functioning of the P system (the clock marks equal time units for the whole system, hence synchronization is possible). While trying to simulate the application of an arbitrary non-cooperative rule with several rules of type a→α, with |α| ≤ 2, one has to accomplish two conditions. Firstly, one has to guarantee that all the objects from αwill eventually be produced. Secondly, these objects must be produced at the “proper” time: all of them in the same moment (a local synchronization) and according with the simulation of other rules that were started at the same time with a→α(a global synchronization). Consequently, the rules presented above are grouped according with their function in the simulation. The first group represents a set of “delaying” rules (they are used while simulating the rules with a shorter right hand side in order to synchronize their executions with those that have the longest right hand side). These rules are “chained”, hence, staring from an object a, an object X(i,t)is produced in exactly tcomputational steps. The second group is responsible for producing in consecutive computational steps the objects a(j1,k−1), a(j2,k−2), . . . , a(jk−1,1), a(jk,1) (in order of their production, the last two being produced in the same time). For an object a(i,l)in this sequence, the index lrepresents the number of computational steps that Πwill perform, starting from its production and until the object aiis produced (see the third group of rules). Finally, one can remark that the objects aj1, aj2, . . . , ajkare produced in the same computational step by Π(while simulating the rule i:a→aj1aj2. . . ajk∈R1). Moreover, all the other rules from Πthat stated at the same moment as i:a→aj1aj2. . . ajk, are simulated in the same manner by Πand their output is produced in the same computational step as mentioned above. Consequently Πcorrectly simulates any computation of Π, hence the theorem holds true. On Catalytic P Systems with One Catalyst 287 4 Catalytic P Systems with One Catalyst and IFTs In what follows we prove that the family of sets of numbers computed by catalytic P systems with only one catalyst is included in the family of the length sets of the languages generated by iterated finite state transducers with at most 3 states. Theorem 2. NIF T3⊇NOP1(cat1). Proof. Given an arbitrary catalytic P system Π= (O, C, w1, R1, i1) such that C= {c}, then one can construct an iterated finite transducer γ= (K, V, q0, a0, F, P) which simulates Πas follows. Without loss of generality we assume that the initial configuration of Πis w1=ca0. Let w=a1a2. . . ambe a string. We denote by Perm(w) = {ai1ai2. . . aim|1≤ij≤m, 1≤j≤m, with ij6=il,1≤j, l ≤m} the set of all permutations of string w, i.e., the set of all strings that can be obtained from wby changing the order of symbols. In addition, let us consider the following sets of objects from O: X={A∈O|(∃)A→α∈R1and (6 ∃)cA →cβ ∈R1}; Y={A∈O|(∃)A→α∈R1and cA →cβ ∈R1}; Z={A∈O|(∃)cA →cα ∈R1and (6 ∃)A→β∈R1}; T={A∈O|(6 ∃)A→α∈R1and (6 ∃)cA →cβ ∈R1}. One can remark that O=X∪Y∪Z∪T∪ {c}. Based on the above settings the IFT γis defined as follows: K={q0, q1, q2}, V=O\ {c}, F={q0}, and the set of rules Pis constructed in the following manner: •for any a∈Twe add to Pthe rule q0a→aq0; •for any a∈X∪Yand a→α∈R1we add to Pthe rules q0a→αq1, where α∈Perm(α); •for any a∈Twe add to Pthe rule q1a→aq1; •for any a∈X∪Yand a→α∈R1we add to Pthe rules q1a→αq1, where α∈Perm(α); •for any a∈Y∪Zand ca →cα ∈R1we add to Pthe rules q1a→αq2, where α∈Perm(α); •for any a∈T∪Zwe add to Pthe rule q2a→aq2; •for any a∈X∪Yand a→α∈R1we add to Pthe rules q2a→αq2, where α∈Perm(α); 288 D. Sburlan •for any a∈Y∪Zand ca →cα ∈R1we add to Pthe rules q0a→αq2, where α∈Perm(α). The construction was designed such that each string processed by γduring its computation will correspond to a configuration of Π. Moreover, one iteration of γ simulates the maximal parallel applications of the rules of Π. If the current string (say w) processed by the IFT is composed only by the symbols from T, then γremains in q0∈Fand stops, accepting the string. This situation corresponds to the halting configuration of Π(that is, Πcontains in its region the multiset cw and no rules can be further applied). In case wcontains symbols form X∪Y∪Z, then γstarts the simulation of the maximal parallel applications of the rules of Π. Since γprocesses strings at each iteration, then the simulation of Πhas to accomplish the following task: all the symbols which are the subject of a rule of Πhave to be processed also by γ. Recall that γprocesses strings and in these strings there might be symbols from T(which are not the subject of any rule) in any position. Consequently, one has be sure that any symbol in a configuration of Πthat is a subject of a rule (non-cooperative or catalytic) has to have the opportunity to be rewritten in the corresponding string processed by γ(by the corresponding rule). This is why, γuses the rules qia→aqi for qi∈Q, 1 ≤i≤3, and a∈T(that is, while processing the string, γ”skips” all the symbols that are not the subject of any rule). In one iteration of γone can apply at most once a rule corresponding to a catalytic rule of Π(recall that the P system functioning semantics define such behaviour). More precisely, assuming that wis the current processed string, we have •either γis in state q0and executes a rule of type q0a→αq2for q1, q2∈Q, a∈Y∪Z,ca →cα ∈R1, and α∈Perm(α). This situation occurs when γ processes w=w1aw2,w1∈T∗, and w2∈(X∪Y∪Z∪T)∗(whas the prefix w1composed only by symbols from T, followed by the symbol a∈Y∪Zthat triggers the simulation of the catalytic rule; the symbols from w2that belong to X∪Ywill trigger only the simulation of the non-cooperative rules). •either γis in state q1and executes a rule of type q1a→αq2for q1, q2∈ Q,a∈Y∪Z,ca →cα ∈R1, and α∈Perm(α)). This situation occurs when γprocesses w=w1aw2, where w1is described by the regular expression T∗(X|Y)(X|Y|T)∗,w2∈(X∪Y∪Z∪T)∗(the symbols from w1and w2that belong to X∪Ywill trigger only the simulation of the non-cooperative rules) . One can also remark that if a configuration wof Πcontains at least one object a∈Z, then in the current computational step a catalytic rule will be executed (because of the maximal parallel applications of the rules); in contrary, if wdoes not contain any symbol a∈Zthen it is not guaranteed that a catalytic rule will be executed (even if wcontains symbols from Y, then, because of the nondeterminism, it might happen that all the rules selected for application are non-cooperative). On the other hand, γsimulates Πby processing strings (hence the order of symbols is precisely defined). The design of γguarantees that, if On Catalytic P Systems with One Catalyst 289 applicable, a rule corresponding to a catalytic rule of Πis executed at most once. The only issue that could appear regards the presence of multiple symbols from Y∪Zin the current string processed by γ(in order to perform a correct simulation, one has to be sure that any of these symbols has a ”chance” to be rewritten). This is why for any rule a→α∈R1or ca →cα ∈R1, the IFT γwill use for the simulation a set of rules of the type qa →pPerm(α). Based on the above theorem, the following result holds true. Corollary 1. If NIFT3⊂NRE then NOP1(cat1)⊂NRE 5 Conclusions In this paper we gave a normal-form theorem for catalytic P systems. We also investigated the relation between P systems with one catalyst and iterated finite transducers. This last topic is of a particular interest because it converts an open problem from the P system framework to an open problem from the string rewriting theory. In addition, the simplicity of the construction gives hopes for solving an open problem stated from the introduction of P systems. Acknowledgements The work of the author was supported by the CNCSIS IDEI-PCE grant, no. 551/2009, Romanian Ministry of Education, Research and Innovation. References 1. Bordihn H., Fernau H., Holzer M., Manca V., Martin-Vide C., Iterated Sequential Transducers as Language Generating Devices, Theoretical Computer Science, 369, 1 (2006), pp. 67–81. 2. Freund R., Kari L., Oswald M., Sosik P., Computationally Universal P Systems Without Priorities: Two Catalysts Are Sufficient, Theoretical Computer Science, 330, 2 (2005), pp. 251–266. 3. Rozenberg G., Salomaa A., eds., Handbook of Formal Languages, 3 volumes, Springer- Verlag, Berlin, 1997. 4. P˘aun G., Computing with Membranes: an Introduction. Bulletin EATCS, 67 (1999), pp. 139–152. 5. P˘aun G., Membrane Computing. An Introduction, Springer-Verlag, Berlin, 2002. 6. P˘aun G., Rozenberg G., Salomaa A., eds., The Oxford Handbook of Membrane Computing, Oxford University Press Inc., New York, 2010. 7. Sburlan D., Further Results on P Systems with Promoters/Inhibitors, International Journal of Foundations of Computer Science, 17 (2006), pp. 205–221.