A Note on P Systems with Activators

A Note on P Systems with Activators Artiom ALHAZOV Research Group on Mathematical Linguistics Rovira i Virgili University Pl. Imperial T´arraco 1, 43005 Tarragona, Spain E-mail: [email protected] Institute of Mathematics and Computer Science Academy of Sciences of Moldova Str. Academiei 5, Chi¸sin˘au, MD 2028, Moldova E-mail: [email protected] Abstract.The usual assumption in P systems behavior is that of maximal parallelism, however in living cells it is not the case because they have a limited number of enzymes. The aim of this paper is to try to merge these ideas by introducing a notion of activator - a formal model of enzyme as a usual symbolobject, more or less a middle notion between a catalyst and a promoter. Each activator executes one (context-free) rule, and can evolve in the same step. The rules will need activators to be applied, so the parallelism of each rule is maximal, but limited to the number of its activators. Such systems can generate any recursively enumerable language or deterministically accept any recursively enumerable set of vectors of nonnegative integers. It is open what is the power of P systems with uniport rules and activators. 1 Introduction: Meet the Activator The idea behind this paper came as an attempt to have a universal theory of objects and rules: let us associate one (non-cooperative) rule to every object, called the activator of that rule, think of enzyme (a biological protein, acting as a catalyst) as its prototype. For a reaction to occur, rewriting one copy of an object into 0 or more objects, one copy of the activator must be present in the region. The reaction is then performed nondeterministically, in the maximally parallel manner. Example: If R1={(a:b→aa),(b:a→λ)}, then [1a3b5]1⇒[1a6b2]1⇒[1a8]1. The important properties are the following: 1. Each object activates one rule (only one context-free rule can be associated to each object). 2. Each rule needs an activator to be performed. 3. The reactant (the object in the left-hand side of the rule) is, clearly, also needed for the rule to be performed. 16 4. The presence of each activator allows one object to be rewritten by the rule it activates. 5. The activator can be itself rewritten (by some activated rule) while itself activating some rule (or while not activating any, if there are no reactants available for it). 6. The parallelism of the activated rules is maximal. The difference of the new notion from the existing ones is that the catalysts cannot evolve, that the promoters promote rewriting of many rules, not just one, and, finally, that a catalyst/promoter can enforce rules from a fixed set, while for the activators this set is restricted to singletons. The biological counterpart of the inspiration for the activators model comes from the following observations: •Each enzyme only performs a certain reaction (or a group of similar actions). •The speed of the reactions depends on the number of enzymes present. •An enzyme can react while performing a reaction. •An enzyme can act on a protein molecule, producing two protein molecules. •An enzyme is itself a protein molecule. 2 Definition We assume the reader to be familiar with the basic notions of membrane computing. We now give a more formal description of the systems with activators. Such a system is written as Π = (O, µ, w1,· · · , wm, R1,··· , Rm, i0), where Ois a finite set of objects, µis the membrane structure with mmembranes, injectively labeled as 1,· · · , m and (wi)1≤i≤mare the initial multisets. i0is the output region (0 if it is the environment). Finally, for every region i,Riis a set of rules of the form (a:b→x), where xis a string of objects with target indications from T={here, out}∪{inj|1≤i≤m}(ais called the activator of such a rule), such that Card{(f:b→x)∈Ri|b∈O, x ∈(O×T)∗}= 1 for every fixed f∈O. (The last restriction comes from the idea that the enzymes usually can only activate a single reaction.) The transition step (in each region iwith a multiset w) is defined as follows: the multiset A={r|w|a|r= (a:b→x)∈R}of activated rules is applied in the maximally parallel manner to w. For every b∈O, min{|w|b,P rrewrites b A(r)}occurrences of bare rewritten. From now on we only consider systems with one region and with external output (hence the result of a computation is a string). Notice that there is a one-to-one correspondence between the rules and objects, so •the rules can be defined as (activating) functions of objects, or •the objects can be defined as the activators of rules. 17 3 Universality Theorem 3.1 P systems with activators generate the family of recursively enumerable languages. Proof. Given a language L∈RE over alphabet T, consider a counter machine Gwith set Cof counters, the start instruction labeled by einit, and the instruction set P, recognizing L. We construct the following P system Π=(O, [1]1, w1, R1,0), O={a, a0|a∈T} ∪ {c, c1, c0|c∈C}∪{#, q, q1, q0, r, r0} ∪ {e, e1, e2, e0, e00 |e∈Lab(P)}, w1=einitr0q0vyz, where vconsists of symbols a0for all a∈T , yconsists of symbols c0for all c∈Cand zconsists of symbols e0e00 for all e∈Lab(P). For e, f, g ∈Lab(P), x∈T∪ {λ},c∈C, instructions (e:read(x), add(c), f, g) are simulated in one step by rules •e0:e→cxfrqq1, •e00 :e→cxgrqq1. Object eis replaced by eor f,xis produced if x6=λ, and the value of counter cis incremented. The “garbage” objects r,qand q1are added for the uniformity, and will be erased immediately. Instructions (e:read(x), sub(c), f, g), are simulated in three steps by the rules below •e0:e→e1qx, e:c→c1, •c0:c1→λ, c1:q→r, e00 :e1→e2, •r:e2→fqq1, q:e2→grq1. Object xis produced if x6=λ,eevolves into e1q, in the same time checking if cis present in the region (in that case one copy of cevolves into c1). Then, if c1was produced, then it is erased, in the same time changing qto r. In the meantime, e1changes to e2. Next, if c was present in the beginning of the simulation of the instruction of the counter machine, then rchanges e2to f, otherwise qchanges e2to g. We also need the following rules: •a0:a→aout,a∈T, •r0:r→λ, q0:q1→λ, q1:q→λ, 18 •X: # →#, X∈ {#, e, e1, e2, c, r} to put the terminal symbols in the environment and to cleanup the extra symbols after the simulation of some instruction is finished. The last group, the dummy rules, is added to fulfill the condition that each object is an activator of some rule. 2 Remark: By a similar technique, simulating deterministic register machines, one can conclude that P systems with activators can deterministically recognize (by halting) any recursively enumerable set of vectors of nonnegative integers (the vectors are represented as multisets of objects, introduced in the membrane before the computation begins). 4 Conclusions and Open Problems While trying to create a uniform system of objects and rules, we have introduced a new form of the cooperation between the symbol-objects (reactant – activator), inspired by the biological analog (chemical – enzyme). These systems can generate RE, and only one membrane is enough. The following open question is of a special interest: what biologically inspired restrictions can be further placed on the general form of the rule a:b→x? For instance, what is the power of such system if only uniport rules (of type a:b→binj,a:b→bout,a:bcome) are allowed? Acknowledgements. The work is partially supported by IST-2001-32008 project “MolCoNet”, as well as the Moldovan Research and Development Association (MRDA) and the U.S. Civilian Research and Development Foundation (CRDF), Award No. MM23034. The author would also like to thank Matteo Cavaliere and Ioan Ardelean for fruitful discussions. References [1] I.I. Ardelean, M. Cavaliere, Modelling biological processes by using a probabilistic P system software, Natural Computing, 2, 2 (2003), 173–197. [2] Gh. P˘aun, Membrane Computing. An Introduction, Springer-Verlag, Berlin, 2002. 19