Rewriting in P Systems: An Algebraic Approach

Rewriting in P Systems: An Algebraic Approach Rodica Ceterchi Faculty of Mathematics and Computer Science, University of Bucharest Academiei 14, RO-010014, Bucharest, Romania [email protected] Summary. We reformulate in algebraic terms the maximal parallel rewriting of symbols which occur inside membranes of a P system. 1 Introduction We relate to the formal definition of a P system with symbol-objects, from Section 3.5 of Chapter 3 of the monograph [2]. We give an equivalent formulation of the symbol-object rewriting rules which occur in one membrane of a P system, reformulation which emphasizes the underlying algebraic structure of commutative monoid with a finite set of generators. We limit ourselves to systems with only one membrane. Thus no dissolving actions are taken into consideration, and no target indications for rules. 2 An Algebraic Reformulation: Symbol Rewriting in One Membrane Let V={a1,· · · , an}be an alphabet. Let us consider (V+,+, λ) the commutative monoid freely generated by V. Denote by φV:V→V+the canonical inclusion of Vin V+,φV(ai) = ai. We recall that V+is the unique (up to isomorphism) commutative monoid which includes V, with the following universality property: for any commutative monoid Mwhich includes Vvia ψ:V→Mthere exists a unique morphism of monoids ρV:V+→Mwhich commutes with φVand ψ, i.e., for which the equalities ρV(ai) = ψ(ai) hold in Mfor all 1 ≤i≤n.ρVis called the canonical morphism. We will use additive notation for commutative monoids. If (M, +,0) is such a monoid and a∈M, for a natural number n,na stands for a+a+· · · +awith n occurrences of a. The elements of (V+,+, λ) will thus be written as w=Pn i=1 miai, for mi∈N. 166 R. Ceterchi Two other commutative monoids, isomorphic to (V+,+, λ) are given by the following: •(V∗/σ, ·, λ), where V∗is the (non-commutative) free monoid generated by V,σ is the equivalence relation defined by commutation of letters, ·is the operation induced on classes by catenation, and λis the class of the empty word. •(Nn,+,0), where Nnis the n-th powerset of natural numbers, with + componentwise addition. This is related to several possible representations of multisets which we recall bellow: •String notation: w=am1 1· · · amn n, and any permutation in this string stands for the same multiset. •Function notation: wis identified with the function Mw:V−→ Nwhich associates to each ai∈Vits “multiplicity” in w,mi=Mw(ai) = |w|ai. A compact representation is as set of pairs {(a1, m1), . . . , (an, mn)}. •Vector notation: wis identified with its Parikh vector (m1, . . . , mn)∈Nn. •Additive notation: w=Pn i=1 miai. In [2] the first three above presentations of multisets are used. The monoid V+is endowed with a natural partial order relation (which is the same order as multiset inclusion) given by: n X i=1 miai≤ n X i=1 m0 iaiiff mi≤m0 ifor all 1 ≤i≤n. In the formalism of [2], Section 3.5, evolution rules are triples (αi, βi, δi), where αi∈V+stands for the left-hand side, βistands for the right-hand side, and is a multiset with target indications, and δi∈ {¬δ, δ}is a symbol indicating the dissolution or non-dissolution of the membrane. Since we have only one membrane, no target indications and no dissolution, such a rule will be reduced to a pair (αi, βi) with αi, βi∈V+. Let {(α1, β1),· · · ,(αn, βn)}be such a set of evolution rules (or symbol rewriting rules), associated to our unique membrane. Let Λ={α1,· · · , αn} ⊂ V+be the subset composed of left-hand sides of the set of rules. Consider RΛ=Λ+the commutative monoid freely generated by Λin V+. Consider µΛ:RΛ−→ V+the canonical morphism given by µ(αi) = αifor all i= 1, . . . , n. Its image µ(RΛ) = MΛis the submonoid of V+generated by Λ= {α1,· · · , αn}. Let w∈V+be a fixed string (the “axiom” of the unique membrane). Consider in MΛthe above partial order and its intersection with the interval [λ, w] w.r.t. this order. (MΛ∩[λ, w],≤Λ) is nonempty and finite. Let CΛ,w denote the set of the maximal elements of (MΛ∩[λ, w],≤Λ). It is nonempty. Let RΛ,w =µΛ −1(CΛ,w). It is nonempty and finite. Rewriting in P Systems: An Algebraic Approach 167 Definition 1. Aone step computation starting with axiom wand applying symbol evolution rules (α1, β1),· · · ,(αn, βn)is: (i) If RΛ,w ={λ}, then nothing happens. (ii) If RΛ,w 6={λ}, then an element m1α1+m2α2+· · · +mnαn∈RΛ,w is chosen at random. (iii)Replace wby z, obtained from was z=w− n X i=1 miαi+ n X i=1 miβi. Lemma 1. The one step computation defined above is the same as the one step transition in a P system with one membrane containing wand symbol evolution rules {(α1, β1),· · · ,(αn, βn)}. Proof. Case (i) corresponds to the situation that the rules are not applicable. The strings zobtained by cases (ii) and (iii) of the above are precisely the strings obtained in one membrane, with initial content w, by the maximal parallel application of the set of rewriting rules (α1, β1),· · · ,(αn, βn), after one step of (nondeterministic) computation (see [2]). ut 3 The Case of String Rewriting We want to see to what extent, and how, the construction of the previous section can be extended to cover the case of string rewriting systems. This reopens the discussion on several types of parallel processing features present in a membrane system. According to [2], we have three levels of parallelism; two of them are shared by the systems with symbols and those with strings, and a third one, specific to string-rewriting systems: •Parallel processing inside one membrane: the rules are applied to all symbols or strings inside a membrane. •Parallel processing at the level of the system: processing occurs simultaneously in all membranes. •Parallel processing of each string: this would mean parallel rewriting of each string, and would be applicable only to string-rewriting systems. This third type of parallelism, specific to Lindenmeyer systems, is not used by P systems: the rules rewrite each string in only one place. If we want to consider this third type of parallelism, i.e. the parallel rewriting of each string, and only one string is present, in one membrane, then we have a non-commutative version of the previous construction. A good candidate for the order relation in terms of which to express maximality is the scattered subwords order. More precisely, for V={a1,· · · , an}an alphabet, consider (V∗,·, λ) the (noncommutative) free monoid generated by V. We consider the partial order relation on V∗given by the scattered subwords of a word: 168 R. Ceterchi uis a scattered subword of v, and we write u≤v, iff there exist a decomposition of uas u=u1· · · unand strings z0, z1,· · · , zn∈A∗such that vcan be decomposed as v=z0u1z1u2z2· · · unzn. For an axiom-string w∈V∗, and a set of string rewriting rules (α1, β1),. . . , (αn, βn), αi, βi∈V∗, one can repeat the construction from the previous section, using the universality property of freely generated non-commutative monoids, and the above partial order, and define, in algebraic terms, the one-step parallel rewriting of one string. If we want to consider the string rewriting systems which are present in the literature, and which have only the first two features of parallelism above, i.e., for which each string is rewritten in only one place, then we will have a different construction. This is a matter of ongoing research. 4 Conclusions and Open Problems Definition 1 is given in purely algebraic terms. Some more intricate notions from Section 3.5 of [2] can be recaptured in this formalism: for instance, (m1, . . . , mn) is an applicability vector (see Definition 3.5.9 of [2]). The formalism can be extended in several directions. First, to deal with several membranes, and next, with the features added by communication between them. Communication in the form of symport/antiport rules can (at a first glance) be more easily adapted to this formalism. Thus ECP systems introduced in [1] seem good candidates. Second, as outlined in Section 3, to deal with string rewriting systems. In the unifying framework of this formalism, the gap between the case of symbol rewriting and the case of string rewriting could be bridged. The concept could also be useful for considering fuzzy extensions. Acknowledgements. The author thanks her colleague Paul Flondor for suggesting the present approach, and for many discussions on this topic. She also thanks the Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence of the University of Sevilla, for a stimulating working environment. This was made possible by project TIN2005- 09345-C04-01 of the Ministerio de Educaci´on y Ciencia of Spain, cofinanced by FEDER funds. References 1. M. Cavaliere: Evolution-Communication P Systems. In Membrane Computing, International Workshop, WMC-CdeA 2002, Curtea de Arge¸s, Romania, August 19-23, LNCS 2597, Springer, 2003. 2. Gh. P˘aun: Membrane Computing. An Introduction. Springer, Berlin, 2002.