Membrane Systems and Time Petri Nets

Membrane Systems and Time Petri Nets Bogdan Aman1, P´eter Batty´anyi2, Gabriel Ciobanu1, Gy¨orgy Vaszil2 1Romanian Academy, Institute of Computer Science Blvd. Carol I no. 8, 700505 Ia¸si, Romania [email protected], [email protected] 2Department of Computer Science, Faculty of Informatics University of Debrecen Kassai ´ut 26, 4028 Debrecen, Hungary [email protected], [email protected] Summary. We investigate the relationship of time Petri nets and different variants of membrane systems. First we show that the added feature of “time” in time Petri nets makes it possible to simulate the maximal parallel rule application of membrane systems without introducing maximal parallelism to the Petri net semantics, then we define local time P systems and explore how time Petri nets and the computations of local time P systems can be related. 1 Introduction There has been several models applied for describing concurrency, communication and synchronization. Two of them are the graph-based model, known later as Petri nets, developed by C. A. Petri [11] and the tree-like model of embedded membranes called membrane or P systems invented by Gh. P˘aun [9]. Petri nets are state/transition systems: places are often used to contain information representing conditions in the system being modeled while transitions are used to represent events that can occur to modify the conditions. Some of the information, the input of the transition, is required for an event to happen, while some other information, the output of the transition, provides the result of the executed transition: they are the output of the transition. A Petri net is a bipartite graph: arcs point from input places to transitions and from transitions to places storing their outputs. There may be some situations where the modelling of a system by conditions and events is not completely satisfactory, for example, when the assumption that all the transitions can take place in an arbitrary order does not describe the system correctly. To model the situation when time delay must be taken into account time Petri nets (TPN) were developed. Concerning time Peri nets, several models were elaborated: time was associated with transitions, places or arcs, etc. We consider the approach adopted by Merlin [8] rendering time to transitions. By this 72 B. Aman et al. model, to every transition twe associate a closed interval [at, bt] such that at, bt∈Q≥0. The transition can fire, if it is enabled and its local time h(t) is such that at≤h(t)≤bt. We adopt the strong semantics, which means that a transition which is enabled either must be fired at some point of the associated interval or it becomes non enabled by firing of another transition. In general, time Petri nets are more powerful than ordinary Petri nets, since time Petri nets are able to simulate Turing machines while, for ordinary Petri nets, this is not possible. Membrane systems are parallel, distributed, synchronized models of computation where embedded membranes are organized in a tree like structure and computation takes place simultaneously in the different membranes in the forms of applications of rewriting rules. The rules evolve in a distributed manner: the application of a rule yields elements with labels, so called messages, which prescribe the exact place where the result of the rule application should move to. An element obtained by a rule application can either remain in the actual membrane, permeate to the parent membrane, or enter into one of its child membranes indicated by the rule. We consider here the basic model, that is, a membrane structure without dissolution rules. In addition we associate to each rule a time interval which gives a lower and an upper values for the time instance when the rule can be executed. We found technically simpler to consider every compartment as if a local stopwatch would operate in that compartment, though the same results could be obtained when we defined a global clock for synchronizing computational steps in the whole membrane system. We call our membrane systems local time membrane systems. In this paper we relate local time membrane systems to time Petri nets such that the image Petri net of a membrane system by this mapping is suitable for answering questions in connection with the membrane system. For example, we can heavily lean on results in the area of time Petri nets concerning questions of reachability, which asks whether a certain configuration of the membrane system can be achieved, or threshold problems, where the question is whether a state can be reached from another in a certain time, or simply finding the paths requiring minimum/ maximum time between any two reachable states (see PopovaZeugmann [14]). There are several timed models for P systems in the literature (see [3], [4], [1]). The attempts for the simulation, up to the present, seem to take the approach similar to timed Petri nets ([6], [1], [2]), where certain values, the delay values, are assigned to rules. This means that the result of a rule application can appear only after that delay assuming a global clock synchronizes the computation of the system. Our model resembles much to that of time Petri nets: an interval is assigned to every rule and a clock local to each compartment synchronizes when the rule can be executed. A computational step is governed by a global clock: only when all membranes finish their action can a new step take place. Membrane Systems and Time Petri Nets 73 2 Membrane systems First of all, we discuss some terminology used in the sequel. A finite multiset over an alphabet Vis a mapping M:V→Nwhere Nis the set of non-negative integers, and M(a) for a∈Vis said to be the multiplicity of ain V. We say that M1⊆M2 if for all a∈V,M1(a)≤M2(a). The union or sum of two multisets over Vis defined as (M1+M2)(a) = M1(a) + M2(a), the difference is defined for M2⊆M1 as (M1−M2)(a) = M1(a)−M2(a) for all a∈V. The multiset Mcan also be represented by any permutation of a string w=aM(a1) 1aM(a2) 2. . . aM(an) n∈V∗, where if M(x)6= 0, then there exists j, 1 ≤j≤n, such that x=aj. The set of all finite multisets over an alphabet Vis denoted by M(V), the empty multiset is denoted by ∅as in the case of the empty set. A membrane system, or P system, is a tree-like structure of hierarchically arranged membranes embedded in the skin membrane as the outermost part of the system. Each region is delimited by a surrounding membrane, they can be arranged in a tree (cell-like [9]) structure or in a graph form (tissue-like [7] or neural-like [5]). In this paper we use the so-called symbol-object P systems [9] without dissolution, that is, each membrane has a label and enclosing a region containing a multiset of objects and rules and possibly some other membranes. The unique outer-most membrane is called the skin membrane. We assume the membranes are labelled by natural numbers {1, . . . , n}, and we use the notation mi for the membrane with label i. Each membrane mi, except for the skin membrane, has its parent membrane, which we denote by µ(mi). As an abuse of notation we use µboth for the parent function and both for denoting the structure of the membrane system itself. The contents of the regions of a P system evolve through rules associated with the regions. The computation of a P system is a locally asynchronous globally synchronous process: each multiset of objects in a region is formed locally by the rules attached to the regions, while a computational step of the whole system is a macro step: it finishes when all of the regions have finished their actions. In the variant we consider in this paper, the rules are multiset rewriting rules given in the form of u→vwhere u,vare multisets, and they are applied in a maximal parallel manner, that is, a region finishes its computation when no more rules can be applied in that computational step. In fact, the computational steps in the regions consist of two parts: first the rule application part and then comes a communication part where all the objects with labels find their correct places. The end of the computation of the system is defined by the following halting condition: a P system halts when no more rules can be applied in any of the regions; the result is a number, or a tuple of natural numbersthe number of certain objects in a membrane labelled as output. Definition 1. AP system of degree n≥1is Π= (O, µ, w1, . . . , wn, R1, . . . , Rn) where -Ois an alphabet of objects, 74 B. Aman et al. -µis a membrane structure of nmembranes, -wi∈ M(O),1≤i≤n, are the initial contents of the nregions, -Ri,1≤i≤n, are the sets of evolution rules associated with the regions; they are of the form u→vwhere u∈ M(O)and v∈ M(O×tar)where tar ={here, out}∪{inj|1≤j≤n}. Unless otherwise stated we consider the n-th membrane as the output membrane. A configuration is the sequence W= (w1, . . . , wn) where wkare the multiset contents of membrane mk( 1 ≤k≤n). Let R=R1∪R2∪ · ·· ∪ Rn, where Ri={ri1, . . . , riki}is the set of rules corresponding to membrane mi. The application of u→v∈Riin the region imeans to remove the objects of ufrom wiand to add the new objects specified by vto the system. The rule application in each region takes place in a non-deterministic and maximally parallel manner. This means that the rule application phase finishes, if no rule can be applied anymore in any region. As a result, each region where rule applications took place, is possibly supplied with elements of the set O×tar. We call a configuration which is a multiset over O∪O×tar an intermediate configuration. If we want to emphasize that W= (w1, . . . , wn) consists of multisets over O, we say that Wis a proper configuration. Rule applications can be preceded by priority check, if priority relations are present. Let ρi⊆Ri×Ri1≤i≤nbe the (possibly empty) priority relations. Then r∈Riis applicable only if no r0∈Rican be applied with (r0, r)∈ρi. We may also denote the relation (r0, r)∈ρiby r0> r. Priority relations will be mentioned only in Remark 2. In the next phase the elements coming from the right hand sides of the rules of region ishould be added to the regions as specified by the target indicators associated with them. If rhs(r) contains a pair (a, here)∈V×tar, then aremains in region i, this is the region where the rule is applied. If rhs(r) contains (a, out)∈ V×tar, then ais added to the parent region of region i. In our membrane systems we assume that the results are formed in a designated membrane, the output membrane, of the system. Unless otherwise stated, we consider mnas the output membrane of the system. If rhs(r) contains (a, inj)∈V×tar for some region j, then ais added to the contents of region j. In the latter case µ(mj) = miholds. 3 The Petri net model By defining a time dependent Petri net model we followed the definition proposed by Popova-Zeugmann [12] and chose a model rendering time intervals to transitions along the original concept of Merlin [8]. First of all, we define the notion of untimed Petri net and then extend this concept to the timed version. Definition 2. A Petri net is a tuple U= (P, T, F, V, m0)such that 1. P,T,Fare finite, where P∩T=∅,P∪T6=∅and F⊆(P×T)∪(T×P), 2. V:F→N>0, 3. m0:P→N. Membrane Systems and Time Petri Nets 75 The elements of Pare called places and the elements of Tare called transitions. The elements of Fare the arcs and Fis the flow relation of U. The function Vis the multiplicity (weight) of the arcs and m0is the initial marking. We may occasionally omit the initial marking and simply refer to a Petri net as the tuple U= (P, T, F, V ). We stipulate that, for every transition t, there is a place psuch that V(p, t)6= 0. In general, a marking is a function m:P→N. Let x∈Por x∈T. The preand postsets of x, denoted by •xand x•, respectively, are defined as •x= {y|(y, x)∈F}and x•={y|(x, y)∈F}. Each arc has an incoming and outcoming multiplicity denoted as follows: Definition 3. Let tbe a transition. We define below two markings, t−and t+, as multisets of places, which govern when a transition can be fired and how many tokens are added to the place pupon firing the transition, respectively. t−(p) = V(p, t),if (p, t)∈F, 0 otherwise ,t+(p) = V(t, p),if (t, p)∈F, 0 otherwise . A transition is said to be enabled, if t−(p)≤m(p) for all p∈P. Applying the notation Mt=t+−t−, we are able to define a firing of the Petri net U= (P, T, F, V ). Definition 4. Let U= (P, T, F, V, m0)be a Petri net and let mbe a marking in U. A transition t∈Tcan fire in m(notation: m−→t), if tis enabled in m. After the firing of t, the Petri net will obtain the new marking m0, where m0=m+Mt. Notation: m−→tm0. We obtain time Petri nets, if we add to the Petri net model information about time attached to transitions. Intuitively, the time associated to a transition will denote the last time when the transition or a transition with common preplace was fired. Though the definitions could be extended to unbounded time intervals also, we are concerned with bounded time intervals this time. Definition 5. A time Petri net (TPN) is a 6-tuple N= (P, T, F, V, m0, I)such that 1. the 5-tuple S(N)=(P, T, F, V, m0)is a Petri net, 2. I:T→Q≥0×Q≥0and, for each t∈T,I(t)1≤I(t)2holds, where I(t) = [I(t)1, I(t)2]. We call I(t)1and I(t)2earliest and latest firing times belonging to t, respectively. Notation: eft(t),lft(t). A function m:P→Nis called a p-marking of N. Observe that talking about ap-marking of Nis the same as talking about a marking of S(N), where S(N) is called the skeleton of Nand, roughly speaking, it is the untimed Petri net obtained from Nby omitting every reference to time. 76 B. Aman et al. Definition 6. 1. A transition marking (or t-marking) is a function h:T→ R≥0∪ {#}. 2. Let N= (P, T, F, V, mo, I)be a time Petri net, map-marking and hatmarking in N. A state in Nis a pair u:= (m, h)such that a) (∀t∈T)(t−m→h(t) = #), b) (∀t∈T)(t−≤m→h(t)∈R≥0∧h(t)≤lft(t)). The initial state is the pair u0= (m0, h0), where m0is the initial marking and h0(t) = 0,if t−≤m0, # otherwise . Definition 7. A transition tis ready to fire in state u= (m, h)(in notation: u−→t), if tis enabled and eft(t)≤h(t). We define the result of the firing of a transition that is ready to fire. Definition 8. Let tbe a transition and u= (m, h)be a state such that u−→t. Then the result of the firing of tis a new state u0= (m0, h0), such that m0=m+4t and h0(ˆ t) =    h(ˆ t),if (ˆ t−≤m, ˆ t−≤m0and •ˆ t∩•t=∅)or t=ˆ t, # if ˆ t−m0, 0 otherwise . In words, the firing of a transition has multiple effects. First of all, it changes the t-marking of the system as it is customary by simple Petri nets. Moreover, the time values attached to the transitions may also change. If ˆ twas enabled before the firing of transition tand ˆ tremains enabled after the firing, moreover ˆ thas no common preplace with the transition which has just been fired, then the value h(ˆ t) for ˆ tremains unchanged. The value h(ˆ t) remains the same even if ˆ t=t. If ˆ tis newly enabled with the firing of transition tor ˆ thas common preplace with tand ˆ tdiffers from t, then we have h(ˆ t) = 0. If ˆ tis not enabled after firing of transition t, then h(ˆ t) = #. Observe that we adopt a stronger condition for hto preserve the value for a transition ˆ tupon firing with transition t. We are not content with the fact that ˆ t should be newly enabled in order to have h(ˆ t) = 0 in the subsequent computational step, but we also demand that tand ˆ tshould not have common preplaces. To ensure multiple executions of the same transition, if ˆ t=t, then h(ˆ t) retains its value after the firing step. Besides the firing of a transition there is another possibility for a state to alter, and this is the time delay step. Definition 9. Let tbe a transition and u= (m, h)be a state and τ∈R+. Then elapsing of time with τis possible for the state u(in notation: u−→τ), if for all t∈T,h(t)6= # implies h(t) + τ≤lft(t). Then the result of the elapsing of time by τis defined as follows: u−→τu0= (m0, h0), where m=m0and h0(ˆ t) = h(ˆ t) + τ, if ˆ t−≤m0for an arbitrary ˆ t∈T, # otherwise. Membrane Systems and Time Petri Nets 77 Observe that the definition of the result of a time elapse ensures that we are not able to skip a transition when it is enabled: a transition cannot be made not enabled by a time jump. Finally, we define the notion of a feasible run in a time Petri net. Definition 10. Let N= (P, T, F, V, mo, I)be a time Petri net, assume σ= t1. . . tnis a sequence of transitions and τ=τ0τ1. . . τn(τi∈R≥0)be a sequence of times. Then σ(τ)τ0t1τ1. . . tnτnis called a run. σ(τ)is a feasible run, if there are states s= (m, h)and s0= (m0, h0)such that s−→∗ σ(τ)s0. We may omit the argument τfrom σ(τ)if it is clear from the context. Obviously, classic Petri nets can be obtained when h(t) = [0,0] for every transition and no time delay step is ever made. 4 Relating the Petri net model to the membrane system First, we show how to establish a correspondence between the P system model without time and the model of time Petri nets. As the first step we give the underlying structure of the Petri net associated to a membrane system. The correspondence described below seems to have appeared first by Kleijn, Koutny and Rozenberg [6]. They define the correspondence by limiting the results of the Petri net computations only to those which can be obtained by a sequence of maximal parallel or maximally enabled transition steps. A step is a multiset of transitions and a transition is maximally enabled, if it is enabled and is not a proper subset of an enabled step. They establish a close correspondence between Petri nets with maximally enabled (max enabled) steps and membrane systems. Moreover, other semantics like locally enabled steps or minimal enabled steps could be considered. In this case we preserve the original semantics for Petri nets: the fireable transitions can be executed in any order. This involves that we have to make essential use of the timed model, since ordinary Petri net model is not Turing complete in contrast to the general membrane system. Definition 11. Let Π= (O, µ, w1, . . . , wn, R1, . . . , Rn)be a membrane system. Then we define the following places and transitions for the Petri net. 1. P=P0∪P∗ 0∪ {sto, ste, sem}, where P0=V× {1, . . . , k}and P∗ 0=V∗× {1, . . . , k}. We set m0(p) = wj(a)for every place p= (a, j). Intuitively, the places V× {1, . . . , k}correspond to the objects of Vlabelled by the indexes of the membranes and the places in V∗× {1, . . . , k}correspond to the objects on the right hand sides of Ri(1 ≤i≤n)labelled by messages. The places ste, sto, sem are additional places which serve for the synchronization of the Petri net model. 2. T=T0∪T∗ 0∪ {to, te, t1 sem, t2 sem}, where the sets of transitions T0and T∗ 0are detailed in the subsequent parts of the definition and {to, te, t1 sem, t2 sem}are auxiliary transitions to be specified later. Let rl∈Ri, where l∈ {1, . . . , nki}. 78 B. Aman et al. Then let ti ldenote the transition corresponding to rland T0={ti l|1≤i≤ n, 1≤l≤ki}. A transition ti lconnects elements of P0to P∗ 0: if p= (a, j), then V(p, ti l) = lhs(rl)(a), if i=j, and V(p, ti l) = 0 otherwise. Furthermore, if p∗= (a∗, j),V(ti l, p∗) = rhs(rl)(a), if i=j,V(ti l, p∗) = rhs(rl)(a, out), if j=parent(i)and V(ti l, p∗) = rhs(rl)(a, inj), if i=parent(j)and V(ti l, p∗) = 0otherwise. Likewise, T∗ 0={si j|1≤i≤k, 1≤j≤n}are such that {•(si j)|1≤i≤k, 1≤j≤n}=P∗ 0,{(si j)•|1≤i≤k, 1≤j≤n}=P0and, if ai∈Oand 1≤j≤n, then p∗= (ai, j)∗and V(p∗, si j) = V(si j,(ai, j)) = 1 and all the other values are 0. The transitions t1 sem and t2 sem, belonging to the semaphore, will be treated in the section. 3. The intervals belonging to the elements of T=T0∪T∗ 0are [0,0], the transitions aiming for the synchronization have various time intervals to be specified later. In words, we simulate the rule rl∈Riwith transition ti lsuch that the weights of the arcs reflect the multiplicities of the elements in compartment i, and the transitions sk jensure the correct reordering of the elements with messages when the rewriting phase is finished. If we term the rule application phase as the odd and the communication phase as the even part of the operation, we obtain two Petri nets for the subsequent phases of the simulation, which are illustrated in Figures 1 and 2. A little more detailed, the complete Petri net acts as follows. The two main sets for the places correspond to the objects of the membrane system. If ai∈V has kioccurrences in mj, then, for p= (ai, j), m(p) = ki. Likewise, assume at the end of a rule application phase we have k0 ioccurrences of (ai, here) in mj, and k00 ioccurrences of (ai, out) in ml, where j=parent(l) and k000 icopies of (ai, inj) for l=parent(j), then m(p∗) = k0 i+k00 i+k000 i, where p∗= (ai, j)∗. At the rule application phase the element stocontrols the process: if there are any transitions that are enabled, then they are executed. Otherwise a time elapse is applied and a token from stois passed over to sem at time 1. The situation is similar with the communication phase: if every element has found its correct place, then no more transition sj iis possible and stegives control to sem by passing a token to sem at time instance 1. We ensure the globally asynchronous locally synchronous character of the membrane system for the Petri net by defining a semaphore which governs the distinct groups of membrane transitions, like rewriting phase, where objects are replaced in accordance with rewriting rules, or communication phase, where objects labelled with tags inj, here, out find their correct places. In what follows we define the timed part of the Petri net that provides the synchronization. Assume the semaphore is denoted by the tuple Sem = ({sem}, R, Fsem, Vsem, I). In some sense the semaphore divides the rule application and communication parts of the operation of the P system. The place sem of the semaphore is the place where this choice takes place. The place sem obtains either one or two tokens. Membrane Systems and Time Petri Nets 79 stop1p2 to [1,1] t1 [0,0] sem p∗ 1p∗ 2 2 Fig. 1. The Petri net simulating the rule application part of a membrane computational step. sem p1p2 te [1,1] 1 t∗ 1 [0,0] t∗ 2 [0,0] step∗ 1p∗ 2 Fig. 2. The Petri net simulating the communication part of a membrane computational step. 86 B. Aman et al. rules corresponding to the chosen transitions form a maximal parallel set of rules. If at the end of the rule application phase at least one rule remains that could be applied, then our choice is obviously not a maximal parallel set of rules. In order to ensure the correct simulation, in this case the Petri net enters into an infinite loop of transitions when reaching state perp˜ tprovided ˜ tcould be applied. Otherwise, control is given back to the semaphore. Figure 5 details the Petri net which is in fact a sub net of the one in Figure 4. qi Bp1p2 tfini [1,1] ¯ t [0,0] finiperp¯ t 2 [0,0] Fig. 5. The Petri net deciding whether a maximal parallel set of rules is reached. Finally, Figure 6 gives an overall picture of the odd part of the simulating Petri net. The place stostimulates the odd phase and tokens are immediately distributed among the places qi 0, which initiate the simulations of the computations in membranes mi(1 ≤i≤n). When the computation in miis over, in the simulating Petri net the place finiobtains a token. If all the places fini(1 ≤ i≤n) have collected their tokens, then a token is passed over to sem and a new computational phase begins. We remark that the construction above gives a general method for simulating any time Petri net defined with the weak semantics by a time Petri net understood with the strong semantics. The case for the membrane system with the strong semantics is possibly a bit simpler, since it is closer to the original semantics of the Petri net model. We define in the next definition the simulating Petri net for a local time membrane system with the strong semantics. The construction is very similar to the ones of the previous subsection, probably it is a little bit easier this time. The only difficulty is to tell when a maximal parallel step is finished. For this purpose, before choosing Membrane Systems and Time Petri Nets 87 st0 [0,0] [0,0] . . . [0,0] q1 0q2 0 . . . qn 0 . . . fin1fin2 . . . finn [0,0] sem Fig. 6. The overall structure of the Petri net for the weak semantics the next transition, we implement a test whether there are transitions that could be executed. This involves creating a new copy of the Petri net simulating the left hand sides of the membrane system rules. Moreover, to keep ourselves to the interpretation of the membrane computational step by distinguishing the computational sequences in the different compartments, we assume that there are nsub Petri nets modelling the computations in the different membranes. We detach, as usual, the odd and even phases of the computation. In the odd phase, the token in stois immediately distributed to the places sti ohence initializing the computation in the sub Petri nets corresponding to membranes mi. Definition 18. Let Π= (V, µ, w1, . . . , wn, R1, . . . , Rn,I)be a local time membrane system with the strong semantics. 88 B. Aman et al. 1. Pcontains P0and P∗ 0, where P0=V× {1, . . . , n},P∗ 0=V∗× {1, . . . , n}, where a∈Vand (1 ≤j≤n)are in Definition 11. As usual, P0represents the actual configuration of the membrane system. We set m0(p) = wj(a)for every place p= (a, j). As before, the places in V×{1, . . . , n}correspond to the objects on the left hand sides of Ri(1 ≤i≤n)of the membrane rules, while the elements of V∗× {1, . . . , n}correspond to the objects on the right hand sides of the membrane rules labelled by messages. There are auxiliary places, namely those of the semaphore and ste,sti o,cati: they govern the simulation of the rule application and communication phases. 2. Tconsists of T0,T∗ 0,e T0and some auxiliary transitions. As before, let rl∈Ri, where l∈ {1, . . . , nki}. Then let ti ldenote the transition corresponding to rl and T0={ti l|1≤i≤n, 1≤l≤ki}. A transition ti lconnects elements of P0to P∗ 0: if p= (a, j), then V(p, ti l) = lhs(rl)(a), if i=j, and V(p, ti l) = 0 otherwise. Furthermore, if p∗= (ai, j)∗, then V(ti l, p∗) = rhs(rl)(a), if i=j, V(ti l, p∗) = rhs(rl)(a, out), if i=parent(j)and V(ti l, p∗) = rhs(rl)(a, inj), if j=parent(i)and V(ti l, p∗)=0otherwise. Moreover, (cati, ti l),(ti l, sti o), (sti o, tcati),(tcati, cati)∈F. T∗ 0={si j|1≤i≤k, 1≤j≤n}is defined as before: we let {•(si j)1 ≤ i≤k, 1≤j≤n} | =P∗ 0,{(si j)•|1≤i≤k, 1≤j≤n}=P0and V((p∗ i, j), si j) = V(si j,(ai, j)) = 1, where p∗ i= (ai, j)∗, and all the other values be 0. As to the auxiliary places and transitions, sti oand stehave to check whether there are transitions left to fire. For stethis is easy: steconnects to each transition in T∗ 0, that is, (ste, si l),(si l, ste)∈Fand steconnects to sem by (ste, tre), (tre, sem)∈F. The places sti oneed to make a similar check concerning maximal parallel execution: (sti o,˜ ti l)∈F,(˜ ti l, cati)∈Fand ˜ ti lare such that the connections with the elements of P0are the same as in the case of P0and T0 with the same multiplicities, as well. However, ˜ ti ldo not point to P∗ 0, they give back all the tokens to P0after any of the transitions ˜ ti lhas been fired. When no transition ˜ ti lis able to fire, sti oforwards a token to finiand, when each fini (1 ≤i≤n)possesses a token, they give control back to sem by (fini, mono), (mono, sem)∈F. That is, monofires only if every sub Petri net assigned to membrane mifinishes its computation. 3. Concerning the intervals: the intervals belonging to the elements of T∗ 0are [0,0]. If ti l∈T0, then I(ti l) = I(ri l). Furthermore, I(fini) = I(fine) = [1,1]. All the remaining intervals are [0,0]. The semaphore is the same as by the case of the core model. We illustrate the sub Petri net corresponding to miin Figure 7. Let Π= (V, µ, u1, . . . , un, R1, . . . , Rn,I) be a local time membrane system. If Πis considered with the weak semantics, then let Nw(Π) denote the time Petri net associated to Πaccording to Definition 17. If Πis understood with the strong semantics, then let Ns(Π) denote the Petri net assigned to Πin accordance with Definition 18. Furthermore, if (w, T) is a proper configuration of Π, let (ν(w), ν(T)) be the configuration of Nw(Π) or of Ns(Π), where Membrane Systems and Time Petri Nets 89 sti ocatip1p2 fini [1,1] t] 1 [0,0] t1[I(t1)−,I(t1)+] sem p∗ 1p∗ 2 2 Fig. 7. The Petri net for a local time membrane system with the strong semantics ν(w)(ai, j) = w(j)(i) and ν(T)(ti l) = T(rl), where rl∈Ri. In addition, if p∗= (a∗ i, j), let ν(w)(p∗) = 0, as (w, T) is a proper configuration. Moreover, if W= (w0,T0)⇒(w1,T1)⇒. . . ⇒(wk,Tk) is a configuration sequence of Π, then ν(W)=(ν(w0), ν(T0)) −→ (ν(w1), ν(T1)) −→ . . . −→ (ν(wk), ν(Tk)) is the corresponding sequence of configurations of Nw(Π) or Ns(Π). If Wis a sequence of proper configurations, then we omit the values Tiand ν(Ti) from the configurations (w, T) and (ν(w), ν(T)i), respectively, since, in this case Tj=T0, where T0(r) = 0 for every r∈R. Theorem 3. Let Π= (V, µ, u1, . . . , un, R1, . . . , Rn,I)be a local time membrane system. 1. Let W=w0⇒w1⇒. . . ⇒wkbe a computational sequence with the weak semantics. Then w0⇒∗ Wwk⇔Nw(w0)−→∗ ν(W)Nw(wk). Moreover, τ(ν(W)) = τ(W)+3k, where τ(W)and τ(ν(W)) are the total time for Wand ν(W), respectively. 2. Let W=w0⇒w1⇒. . . ⇒wkbe a computational sequence with the strong semantics. Then w0⇒∗ Wwk⇔Ns(w0)−→∗ ν(W)Ns(wk). Moreover, τ(ν(W)) = τ(W)+3k, where τ(W)and τ(ν(W)) are the total time for Wand ν(W), respectively. 90 B. Aman et al. Proof. We treat the case of the weak semantics: we give a sketch for the proof of the correctness of our simulation. Assume Π= (V, µ, u1, . . . , un, R1, . . . , Rn,I) is a local time membrane system, let W=w0⇒w1⇒. . . ⇒wkbe a computational sequence with the weak semantics. We prove the theorem by induction on k. -k= 0: there is nothing to prove. -k=l+ 1: Assume we have the statement for l, that is, for the computational sequence Wl=w0⇒σ1w1⇒σ2. . . ⇒σlwlthere exists ξl=m0⇒ m1⇒. . . ⇒mlsuch that µl=ν(wl) and τ(ν(ξl)) = τ(Wl) + 3 ·l, where, for any proper configuration wof Π,ν(w) is defined as above. If qis any place not in P0, then ν(q) = 0, except for sem, where ν(w)(sem) = 1. By the construction of the Petri net h(ti l) = I(ri l) also holds. We extend the correspondence νto the intermediate configurations, as well. The values for the elements of P0are defined as before. As to the values of P∗ 0: ν(w)(a∗ i, j) = w(j)(ai, here) + w(µ(j))(ai, inj) + Pj=µ(l)(ai, out). Let σ(i,s)= τ0r1τ1r2. . . rsτs+1, where r1, . . .,rs∈Ri, be a segment of the selection of mi of length swith the corresponding configurations ((w1,T1),...,(ws,Ts)). Then ξ(i,s)=ν(σ(i,s)) = τ01 . . . τ0k0t1τ11 . . . τ1k1t2. . . tsτ(s+1)1 . . . τ(s+1)ks+1 , where tj correspond to rjin Nw(Π) and τj=τj1+. . .+τjkj, is a computation in Nw(Π). Assume ((m1, h1),...,(ms, hs)) is the sequence of states corresponding to ξi,s, then we claim that ν(w1), . . . , ν(ws) define exactly the same t-markings. For the correspondence of the configurations and t-markings it is enough to prove that, if rcan be executed, then tis ready to fire provided tis assigned to r. By Fact 2, it is enough to observe that Ti(r) = j+afor some j∈Nsuch that r∈Ri jand 0 ≤a≤1, and i− t≤a≤i+ t, where [i− t, i+ t] is the interval corresponding to tas the image of r∈Ri jin accordance with Definition 17. The statement can be proved by examining the various cases for the next step in σi,s.  The converse of the theorem holds, too. We state it in a proposition. Proposition 1. Let N= (P, T, F, V, m0, I)be a time Petri net. Then the following statements are valid. 1. Let Π= (V, µ, u1, . . . , un, R1, . . . , Rn,I)be be a local time membrane system, assume N=Nw(Π). Then, for any proper computational sequence ξof N, there exists computational sequence Wof Πwith respect to the weak semantics such that ξprovides exactly the same output as W. Moreover, τ(ξ) = τ(W) + 3k, where τ(W)and τ(ξ)are the total time for Wand ξ, respectively. 2. Let Π= (V, µ, u1, . . . , un, R1, . . . , Rn,I)be be a local time membrane system, assume N=Nw(Π). Then, for any proper computational sequence ξof N, there exists computational sequence Wof Πwith respect to the strong semantics such that ξprovides exactly the same output as W. Moreover, τ(ξ) = τ(W) + 3k, where τ(W)and τ(ξ)are the total time for Wand ξ, respectively. Membrane Systems and Time Petri Nets 91 Remark 2. We remark that local time weak semantics does not appear to add anything to the computational power of the membrane system, however local time with the strong semantics seems to increase the computational strength of the P system. We conjecture that, by a modification of a proof of P˘aun [10] showing that membrane systems with catalytic rules together with priority define recursively enumerable sets of numbers even with two membranes, it might not be difficult to prove that local time membrane systems with catalytic rules and with the strong semantics define recursively enumerable sets of numbers with two membranes. It is not clear to us, however, how the exact strength of a local time membrane system with the strong semantics could be depicted. 7 Applications The constructions of the previous section makes us possible to apply the results elaborated for time Petri nets for the case of local time membrane systems. Notation 4 Let Π= (V, µ, w1, . . . , wn, R1, . . . , Rn,I)be a local time membrane system. We apply the notation Π=Π?, where ?∈ {w, s}stands for either the weak semantics or the strong semantics, respectively. Definition 19. Let Π?= (V, µ, w1, . . . , wn, R1, . . . , Rn,I)be a local time membrane system. 1. A (possibly intermediate) configuration (w, T)is integer valued, if T(r)∈N for every r∈R. 2. Let mibe a membrane of Π?for some 1≤i≤n. Let σibe a run for mi. Then σiis integer valued if all of its intermediate configurations are integer valued. 3. Let W=w0⇒. . . ⇒wkbe a computational sequence for Π?. Then Wis integer valued, if, for every wi, every run of wiis integer valued. Observe that, given a membrane system Π?and a computational sequence W, the condition that Wis integer valued is equivalent to the requirement that all the time elapses in every run of Ware integers. Proposition 2. Let Π?= (V, µ, w1, . . . , wn, R1, . . . , Rn,I)be a local time membrane system and let w0be a configuration reachable from w. Then w0is integer reachable from w. Proof. Follows from the main theorem together with the corresponding theorem for time Petri nets presented by Popova-Zeugmann ([13], [14]).  Definition 20. Let Π?= (V, µ, w1, . . . , wn, R1, . . . , Rn,I)be a local time membrane system. Then Π?is bounded, if there exists K > 0such that, for every configuration wof Π?,|w(j)|< K (1 ≤j≤n). In other words, Kis an upper bound for the number of elements in every compartment with regard to any configuration w. 92 B. Aman et al. Proposition 3. Let Π?= (V, µ, w1, . . . , wn, R1, . . . , Rn,I)be a local time membrane system, assume Π?is bounded. Then the reachability problem for Π?is decidable. Proof. Follows from Proposition 2.  Proposition 4. Let Π?= (V, µ, w1, . . . , wn, R1, . . . , Rn,I)be a local time membrane system, assume w0is reachable from w. Then the minimum and maximum distances between wand w0are integers. 8 Conclusions In this paper we examined the connections between two models of computations, namely, the membrane systems introduced by P˘aun [9] and time Petri nets defined along the lines of the papers of Popova-Zeugmann ([12],[13]). First of all, we presented a simulation of membrane systems without dissolution by time Petri nets. The novelty in our result is the fact that the simulating Petri nets manage to retain the locality of firing: transitions can be fired one after the other without structural control, like maximal parallelism, imposed on the order of their execution. Next, we defined local time membrane systems on the analogy of time Petri nets, equipping the computational model with two types of semantics. We showed that both kinds of local time membrane systems can be simulated by time Petri nets with the strong semantics. Finally, we mentioned some statements concerning local time membrane systems that are straightforward consequences of the similar results for time Petri nets by reason of the simulations. References 1. B. Aman, G. Ciobanu, Adding Lifetime to Objects and Membranes in P Systems. International Journal of Computers, Communications and Control, 5(3) (2010) 268– 279. 2. B. Aman, G. Ciobanu, Verification of membrane systems with delays via Petri nets with delays. Theoretical Computer Science, 598(C) (2015) 87–101. 3. M. Cavaliere, D. Sburlan, Time and Synchronization in Membrane Systems. Fundamenta Informaticae, 64(1) (2005) 65–77. 4. M. Cavaliere, D. Sburlan, Timeindependent P Systems Towards a Petri Net Semantics for Membrane Systems. Lecture Notes in Computer Science, volume 3365, International Workshop on Membrane Computing, WMC 2004, 239–258, Springer Verlag, Berlin, 2005. 5. M. Ionescu, Gh. P˘aun, T. Yokomori. Spiking Neural P Systems. Fundamenta Informaticae, 71 (2006) 279–308. 6. J. H. C. M. Kleijn and M. Koutny and G. Rozenberg, Towards a Petri Net Semantics for Membrane Systems. Lecture Notes in Computer Science, volume 3850, International Workshop on Membrane Computing, WMC 2005, 292–309, Springer Verlag, Berlin, 2005. Membrane Systems and Time Petri Nets 93 7. C. Mart´ın-Vide, Gh. P˘aun, J. Pazos, A. Rodr´ıguez-Pat´on. Tissue P Systems. Theoretical Computer Science, 296 (2003) 295–326. 8. P. M. Merlin, A Study of the Recoverability of Computing Systems. PhD thesis, University of California, Irvine, CA, 1974 9. G. P˘aun, Computing with Membranes. Journal of Computer and System Sciences, 61(1) (2000) 108–143. 10. G. P˘aun, Membrane Computing - An Introduction, Springer Verlag, Berlin, 2002. 11. C. A. Petri, Kommunikation mit Automaten. Dissertation, Universit¨at Hamburg, Hamburg, 1962. 12. L. Popova, On time Petri nets. Journal of Information Processing and Cybernetics, EIK, 27(4) (1991) 227–244. 13. L. Popova-Zeugmann, Essential States in time Petri nets, InformatikBerichte der HUB, Nr. 96, 1998. 14. L. Popova-Zeugmann, Time and Petri Nets, Springer Verlag, Berlin, 2013.