Self-Stabilization in Membrane Systems

Self-Stabilization in Membrane Systems Artiom Alhazov1,2, Marco Antoniotti1, Rudolf Freund3, Alberto Leporati1, Giancarlo Mauri1 1Universit`a degli Studi di Milano-Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336, 20126 Milano, Italy E-mail: {artiom.alhazov,marco.antoniotti, alberto.leporati,giancarlo.mauri}@unimib.it 2Institute of Mathematics and Computer Science Academy of Sciences of Moldova Academiei 5, Chi¸sin˘au MD-2028 Moldova E-mail: [email protected] 3Faculty of Informatics, Vienna University of Technology Favoritenstr. 9, 1040 Vienna, Austria E-mail: [email protected] Summary. In this paper we study a notion of self-stabilization, inspired from biology and engineering. Multiple variants of formalization of this notion are considered, and we discuss how such properties affect the computational power of multiset rewriting systems. 1 Introduction Membrane systems, also called P systems, are a framework for (bioinspired) computational models, see [4], [5] and [7]. In this paper we consider a one-region rewriting model with symbol objects. In this case, membrane computing can be considered as (maximally parallel or sequential) multiset processing. In general, a computation is a sequence of transitions between configurations. Configurations are multisets, and the transitions are induced by rules, defined by reactants, products and control (additional applicability conditions, if any), viewed as formal computational systems (generating/accepting numeric/vector sets, or computing functions). We will call a property dynamic if it depends on the behavior of a system and cannot be easily derived from its description (as opposed to syntactic properties). Given any finite computation, we assume that the property is easily verifiable. The two usual sources of undecidability are a) that we do not always know whether we are dealing with finite or infinite computations, and b) that some properties are defined on infinite number of computations (due to non-determinism, to the initial input or to some other parameter). In the case of this paper, another source 2 A. Alhazov et al. of potential undecidability is the finite set to be reached as given in the definitions below. Since in this paper we will deal with reachability issues, we would also like to mention the connection with temporal logic [2]. Self-stabilization is a known concept in conventional distributed computing, [8], as well as in systems biology, but as far as we know, it has not yet been considered in the framework of membrane computing. It has been recalled by Jacob Beal during the Twelfth Conference in Membrane Computing, CMC12, and an attempt to formalize it in the membrane computing framework has been done in [1]. The underlying idea is the tolerance of natural and engineering systems to perturbations. The formulation from [8] says: A system is self-stabilizing if and only if: 1. Starting from any state, it is guaranteed that the system will eventually reach a correct state (convergence). 2. Given that the system is in a correct state, it is guaranteed to stay in a correct state, provided that no fault happens (closure). In case of inherently non-deterministic systems, “with probability 1” should be added. Based on this concept, we propose to consider a few formal properties, following the discussion below. In this paper we consider fully cooperative multiset rewriting, possibly with promoters/inhibitors/priorities, operating either in the maximally parallel or the sequential mode. We consider a single working region only, for two reasons. First, the properties of interest are unaffected by flattening the static membrane structure. Second, we would currently like to avoid the discussion about reachability related to “arbitrary configurations” with dynamic membrane structure. 2 Definitions We assume the reader to be familiar with the basics of formal language theory, e.g., we refer to [6]. An alphabet is a finite non-empty set Vof abstract symbols. The free monoid generated by Vunder the operation of concatenation is denoted by V∗; the empty string is denoted by λ, and V∗\ {λ}is denoted by V+. The family of all finite (recursive, recursively enumerable) sets of positive integers is denoted by NFIN (NREC,NRE, respectively). 2.1 Membrane systems A one-region (rewriting) membrane system is a tuple Π= (O, w, R), Self-Stabilization in Membrane Systems 3 where Ois a finite alphabet, w∈O∗is a string representing the initial multiset, and Ris a set of rules of the form r:u→v,u∈O+,v∈O∗. A configuration of the system is represented by a multiset of objects from O contained in the region, and a rule r:u→vis applicable if the current configuration contains the multiset specified by u. Furthermore, applicability may be controlled by promoters (r:u→v|a), inhibitors (r:u→v|¬b), or priorities(r′> r). Throughout the paper, we will use the word control to mean that at least one of these three features is allowed. In such cases, in addition to the availability of ufor a rule rto be applicable, the promoter amust be present in the current configuration, the inhibitor bhas to be absent in the current configuration, and no rule r′with higher priority than ris allowed to be applicable, respectively. A computation step in the sequential mode consists of the non-deterministic application of one applicable rule, replacing its left side with its right side. In the maximally parallel mode, multiple applicable rules have to be applied multiple times, to disjoint submultisets, in a non-deterministic way, possibly leaving some objects idle, under the condition that no further rule is applicable to them. The computation step is denoted by the binary relation ⇒. A computation halts when no rule is applicable to the current configuration (halting configuration). For a generating system, the result of a halting computation is the total number of objects in the system when it halts. The set of numbers generated by a P system is the set of results of its computations. An accepting system is described as (O, Σ, w, R), where Σis an input alphabet: instead of w, the computation starts with wx,x∈Σ∗, and its result is |x|if it halts. The set of numbers accepted by a P system is the set of results of its computations for all x∈Σ∗. 2.2 Self-stabilization and related properties We now resume the discussion started at the end of the Introduction. Clearly, “a correct state” should be rephrased as “a configuration in the set of correct configurations”. Moreover, we would like to eliminate the set of correct states, let us denote it by S, as a parameter. We say that our property holds if there exists some finite set Sof configurations satisfying the conditions 1 and 2 above. Since membrane systems are inherently non-deterministic, we additionally propose two weaker degrees of such a property: possible (there exists a computation satisfying the conditions), almost sure (the conditions are satisfied with probability 1 with respect to non-determinism). Finally, if condition 2 is not required, we call the corresponding property (finite) set-convergence instead of self-stabilization. We now give the formal definitions from [1]. Definition 1. A P system Πis possibly converging to a finite set Sof configurations iff for every configuration Cof Πthere exists a configuration C′∈Ssuch that C⇒∗C′. Definition 2. A P system Πis (almost surely) converging to a finite set Sof configurations iff for every configuration Cof Πthe computations starting in C reach some configuration in S(with probability 1, respectively). 4 A. Alhazov et al. Definition 3. A P system Πis possibly closed with respect to a finite set Siff for every non-halting configuration C∈Sthere exists a configuration C′∈Ssuch that C⇒C′. Definition 4. A P system Πis closed with respect to a finite set Siff for every non-halting configuration C∈S C ⇒C′implies C′∈S. We say that a system is (possibly, almost surely) set-converging if it is (possibly, almost surely, respectively) converging to some finite set of configurations. We say that a system is possibly self-stabilizing if it is possibly converging to some finite set Sof configurations and if it is possibly closed with respect to S. We say that a system is (almost surely) self-stabilizing if it is (almost surely, respectively) converging to some finite set Sof configurations and if it is closed with respect to S. The examination of computational aspects of these properties motivates us to add “weakly” to the properties proposed in [1] – (possibly, almost surely) converging, (possibly) closed, (possibly, almost surely) set-converging, (possibly, almost surely) self-stabilizing – if the corresponding conditions over configurations Conly spans the reachable non-halting ones. Another comment we can make on “almost sure” it that such a property may depend on how exactly the transition probability is defined. The easiest way is to assign equal probabilities to all transitions from a given configuration. Alternatively, to a transition via a multiset of rules rn1 1· · · rnm mwe may assign the weight of a multinomial coefficient (n1+···+nm n1,··· ,nm)=(n1+···+nm)! n1!···nm!, which will make the corner cases less probable than the average ones. There can be other ways to define transition probabilities, but we would like to discuss the properties of interest without fixing a specific way. We assume the transition probabilities in an independent subsystem are the same as if it were the entire system. An important assumption we impose on the probability distribution is that the probability of each transition is uniquely determined by the associated multiset of rules and by the set of all applicable multisets of rules, yet it does not depend on the objects that cannot react, or by the previous history of the computation. 2.3 Register machines In what follows we will need to simulate register machines; here we briefly recall their definition and some of their computational properties. A register machine is a tuple M= (m, B, l0, lh, P ), where mis the number of registers, Pis the set of instructions bijectively labeled by elements of B,l0∈Bis the initial label, and lh∈Bis the final label. The instructions of Mcan be of the following forms: •l1: (ADD (j), l2, l3), with l1∈B\ {lh},l2, l3∈B, 1 ≤j≤m Increase the value of register jby one, and non-deterministically jump to instruction l2or l3. This instruction is usually called increment. Self-Stabilization in Membrane Systems 5 •l1: (SUB (j), l2, l3), with l1∈B\ {lh},l2, l3∈B, 1 ≤j≤m If the value of register jis zero then jump to instruction l3, otherwise decrease the value of register jby one and jump to instruction l2. The two cases of this instruction are usually called zero-test and decrement, respectively. •lh:HALT . Stop the execution of the register machine. A register machine is deterministic if l2=l3in all its ADD instructions. A configuration of a register machine is described by the contents of each register and by the value of the program counter, which indicates the next instruction to be executed. Computations start by executing the first instruction of P(labeled with l0), and terminate with reaching a HALT -instruction. Register machines provide a simple universal computational model [3]. Register machines can be used as accepting or as generating as well as as decision devices. In accepting register machines, a vector of non-negative integers is accepted if and only if the register machine halts having it as input. Usually, without loss of generality, we may assume that the instruction lh:HALT always appears exactly once in P, with label lh. In the generative case, we start with empty registers and take as results of all possible halting computations. Being used as decision devices, register machines may halt in an accepting state with label lyes or in a rejecting state lno, respectively In the following, we shall call a specific model of P systems computationally complete if and only if for any register machine Mwe can effectively construct an equivalent P system Πof that type simulating each step of Min a bounded number of steps and yielding the same results. 3 Results 3.1 Accepting systems For the following theorem we consider any computationally complete model of P systems as defined above, e.g., a model with maximally parallel multiset rewriting or with controlled sequential multiset rewriting. Theorem 1. If a model of P systems yields a computationally complete class, then weakly self-stabilizing subclass accepts exactly NREC. Proof. For any recursive number set there is a register machine Mwith one accepting state qyes and one rejecting state qno, deciding it. We modify the register machine in order to obtain a register machine M′which, once the decision is made, i.e., qyes or qno has been reached, erases the workspace and then enters q′ yes or q′ no respectively, thereby halting in q′ yes if and only if the input is accepted or performing an infinite loop with q′ no : (SUB (1) , q′ no, q′ no) if and only if the input x is rejected. This register machine M′now can be simulated with a P system Π, which by construction starts with a configuration representing the input xand will either end with halting in a configuration representing the state q′ yes or else looping in a configuration representing the state q′ no, i.e., Πis weakly self-stabilizing. 6 A. Alhazov et al. Conversely, consider a self-stabilizing P system Π, i.e., for each input x,Π performs a computation that ends up in a configuration from a finite set Sand then cannot reach any other configuration outside S. Now consider the derivation graph for all possible computations of Πon the input x, i.e., the nodes of this directed graph represent the configurations and the edges indicate the derivation steps from one configuration to the next one during one of these computations. As the number of configurations directly derivable from any configuration in Πis finite, this derivation graph is a connected directed graph with finite degree (from each node, only a finite number of edges is leaving); moreover, this graph cannot have a simple path (a path visiting each node at most once) which is infinite, as every computation in Πhas to reach a configuration (node) from Sand then cannot leave the set of configurations Sany more. Due to K¨onig’s lemma4, the total number of nodes (configurations) in the derivation graph must be finite. Hence, even without knowing the set S, the brute force algorithm computing all possible transitions from the initial configuration, but halting as soon as the system halts or a configuration already passed previously is reached, yields a decision procedure for the set accepted by Π. Strengthening this result by removing “weakly” is problematic, even if more powerful P systems are used. Indeed, self-stabilization also from unreachable configurations would need to handle not only the configurations without any state or with multiple states (which could be handled with the joint power of maximal parallelism and priorities), but also configurations representing a situation with only one state which is not the initial state of the underlying register machine. We have to leave this question open. Theorem 2. If a model of P systems yields a computationally complete class, then the weakly almost surely self-stabilizing P systems of this class accept exactly NRE. Proof. We start with the construction from Theorem 1. We want to show that relaxing the property “weakly self-stabilizing” to “almost surely” leads from recursiveness to computational completeness. It suffices to handle the case when the system rejects the input by never halting. We modify the underlying register machine as follows: add a non-deterministic transition from every state p∈Qto a new state e5, from eerase the contents of all registers and then jump back to e. This will not affect the accepting power, but it will provide a self-stabilizing path from any reachable non-halting configuration. 4K¨onig’s lemma: Let Gbe a connected graph with finite degree. If Gcontains an infinite number of nodes, then it contains an infinite simple path. 5The transition from pto ecan be done by p: (ADD(j), e, e), since the registers then are emptied anyway. Furthermore, the basic model of register machines does not allow non-determinism other than p: (ADD(j), q, r). The branching at ADD instructions might be done by assuming the original computation to be deterministic and replacing p: (ADD(j), q, q) by p: (ADD(j), q, e). The branching at a SUB instruction p: (SUB(j), q, r) may be done by the sequence of rules p: (ADD(j), e, p′), p′: (SUB(j), p′′ , p′′ ), p′′ : (SUB(j), q, r). Self-Stabilization in Membrane Systems 7 The probability that the computation does not self-stabilize for more than k steps decreases exponentially with respect to k. Indeed, the simulation of a register machine by P system has bounded parallelism, each instruction is simulated in a bounded number of steps, and at least one path leads to self-stabilization. Moreover, there only exists a finite number of different sets of applicable multisets containing a branching from the simulation into the self-stabilization path, so the minimum probability for this self-stabilization path is strictly positive. These observations conclude the proof.  Theorem 3. If a model of P systems yields a computationally complete class, then the class of all almost surely self-stabilizing maximally parallel/sequential P systems with priorities accepts exactly NRE. Proof. Given a set Lfrom NRE, we first construct a P system Πsimulating a register machine Maccepting Land then extend Πto a P system Π′even fulfilling the condition of being almost surely self-stabilizing. Let M= (m, B, l0, lh, P ) a deterministic register machine accepting L. We now construct the P system Π= (O, l0, R, >) with priorities accepting L: O=B∪ {ai|1≤i≤m}, R={l1→ajl2|l1: (ADD (j), l2)∈P} ∪ {ajl1→l2, l1→l3|l1: (SUB (j), l2, l3)∈P} >={ajl1→l2> l1→l3|l1: (SUB (j), l2, l3)∈P}. The contents of a register i, 1 ≤i≤m, is represented by the number of symbols aiin Π. The state lof the register machine is represented by the corresponding symbol lin Π, too. When Mhalts in lhwith all registers being empty, Πalso halts with the configuration {lh}. Obviously, Πaccepts L, both in the sequential as well as in the maximally parallel mode. To strengthen the result to even non-weak almost sure self-stabilization, we have to take into account the non-reachable configurations, too. The almost surely self-stabilizing P system Π′= (O′, l0, R′, >′) with priorities accepting Lis constructed as follows: O′=B∪ {ai|1≤i≤m}∪{e}, R′={l1→ajl2|l1: (ADD (j), l2)∈P} ∪ {ajl1→l2, l1→l3|l1: (SUB (j), l2, l3)∈P} ∪ {ai→e|1≤i≤m}∪{ex →e|x∈O′}∪{e→e} ∪ {l→e|l∈B\ {lh}} ∪ {ll′→e|l, l′∈B}, >′={ajl1→l2> l1→l3|l1: (SUB (j), l2, l3)∈P} ∪ {ex →e > r, ll′→e > r |l, l′∈B, x ∈O′, r ∈R} ∪ {l→e > ai→e|l∈B\ {lh},1≤i≤m} ∪ {r > e →e|r∈R′\ {e→e}} . In addition to the idea of the construction given in the proof of Theorem 2 using the exit eby applying a rule l→e,l∈B\ {lh}, it suffices to self-stabilize 8 A. Alhazov et al. from the configurations with no state and from the configurations with multiple states of the register machine. Multiple states can be reduced by the rules ll′→e, l, l′∈B. If no state symbol is present, then we may exit with one of the rules ai→e, 1 ≤i≤m. All remaining cases can be captured by the rules ex →e, x∈O′. By construction, the self-stabilizing set Sequals {{lh},{e}}. The whole construction again is valid for the sequential as well as the maximally parallel mode.  An open question is whether priorities in Theorem 3 can be replaced by promoters or inhibitors. 3.2 Generating systems Theorem 4. Any finite set Mof numbers can be generated by some self-stabilizing membrane system without control. Proof. Consider a P system Π= ({s, a}, s, R), where R={s→an|n∈M} ∪ {amax(M)+1 →λ, ss →s}. It is not difficult to see that Πgenerates Mand (taking S={an|n≤max(M)}∪ {s}) it is self-stabilizing.  Since self-stabilization implies set-convergence and closure, and relaxing either property (to possibly, almost surely and/or weakly) does not compromise the construction of the P system descibed in the proof of Theorem 4, the lower bound on the generative power of associated systems restricted to any property we have defined, is at least NF IN . Lemma 1. A possibly finite set-converging system only generates finite sets. Proof. It follows from Definition 1 that for a system possibly converging to a set S,Scontains all halting configurations. Since Sis finite, so is the set of all the halting configurations. Hence, at most NF IN can be generated.  Theorem 5. Any of the following classes of P systems dpOP m(c)generate exactly NF IN : •dis possibly/almost surely/ - •pis self-stabilizing/finite set-converging •mis maximally parallel/sequential •cis uncontrolled/with promoters/with inhibitors/with priorities. Proof. The claims of the theorem directly follow from Theorems 4 and 5. We now proceed to weak properties of generative systems. Theorem 6. Weakly almost surely self-stabilizing P systems generate exactly NF IN . Self-Stabilization in Membrane Systems 9 Proof. The lower bound is shown by Theorem 4. Now take a weakly self-stabilizing P system Π, and its associated set Sfrom the definition of the property. Consider an arbitrary halting computation of Π. Let Cbe the configuration of Πone step before the halting. Interpreting finite set-convergence for Cimplies that the halting configuration belongs to S. Since the halting computation has been arbitrarily chosen, the set of all halting configurations is a subset of S, and hence it is finite. Therefore, the set generated by Πis finite, too.  Theorem 7. If a model of P system yields a computationally complete class, then weakly possibly self-stabilizing subclass generates NRE. Proof. Consider the construction from Theorem 2, but for a generative P system. The simulation of the underlying register machine is carried out until some point. Unless the P system has already halted, it always has a choice to self-stabilize and loop.  4 Conclusions We have presented some results concerning the concept of self-stabilization, recently proposed for membrane computing. Its essence is in reachability and closure of a finite set. Some of the obtained results can be summarized in the following table: Property computationally complete (sequ/maxpar)+pri Thm self stabilizing acc. ?/gen. NF IN -/5 almost surely s.s. acc. ?/gen. NF IN acc. NRE/gen. NF IN 3/5 possibly s.s. acc. ?/gen. NF IN acc. NRE/gen. NF IN 3/5 weakly s.s. acc. NREC/gen. N F IN 1/6 weakly almost surely s.s. acc. NRE/gen. NF IN 2/6 weakly possibly s.s. acc. NRE/gen. NRE 2/7 One of the questions we proposed is whether priorities may be replaced by promoters or inhibitors in Theorem 2. Another open question is the power of accepting with unrestricted self-stabilization, even if maximal parallelism is combined with priorities (a comment after Theorem 1 and the first question mark in the table above). The other open questions are also marked with question marks in the table above. Any system in the corresponding classes must (besides doing the actual computation) converge (definitely, in probability or possibly) to some finite set from anywhere, without using the joint power of maximal parallelism and control. We mention two topics that we do not deal with here. One is considering the finite set as a parameter, possibly leading to a discussion in model checking. The other one concerns reachability questions in dynamic membrane structures.