Process of Petri Nets Extension

Vol.11 No.2 2006 351-354WUJNSWuhan University Journal of Natural SciencesArticle ID: 1007-1202(2006)02 -0351-04Process of Petri Nets Extension0 Introduction口ZHOU Guofu, HE Yanxiangt ,DU Zhuominany new computing platforms, such as the local areaSchool of Computer, Wuhan University, Wuhan 430072，M;network, Internet and the virtual network, are beingHubei, Chinacreated and the network computing has been popular. There-fore, the semantics model based on such platforms is differentAbstract: To describe the dynamic semantics for the net-to the traditional model. Compared with the traditional model,work computing, the concept on process is presented based onthe semantic model with variable, resource and relation. Ac-the network computing model has two special features: first-cordingly, the formal definition of process and the mappingly, computing units (to fulfill a task) are allocated on the dis-rules from the specification of Petri nets extension to processtributed and independent nodes and these nodes possessare discussed in detail respetively. Based on the collectivesources respectively. Furthermore, the central control node isconcepts of process, the specification of dynamic semantics al-so is constructed as a net system. Finally， to ilustratenot necessary. Secondly， the interactions among computingprocess intuitively, an example is specified completely.units are a kind of active interaction instead of the passive in-Key words: network computing; computing model;teraction controlled by the central node. Accordingly, a modelprocess; Petri netsCLC number: TP 301.2for network computing is presented in Ref, [1].In Petri nets, process is an observational record of systemrun, and it describes the system behavior completely and accu-rately-2-4l. Therefore, process is an important method to un-cover the dynamic semantics of system. Based on the mappingrules discussed in this paper, we can construct occurrence netwhich is similar to that of Petri nets. Consequently, we cananalyze and verify the dynamic semantics through the theoriesand methods of occurrence net. Based on Ref.[1], in this paper, the definition and the graphic representation of processare presented respectively.1 Petri Nets ExtensionReceived date: 2005-04-20Based on the traditional computing model-5-8]， we pres-ndation item: Supported by Technology Innovation Fundation ofent a seman中国煤化工mpuing which is com-Wuhan UniversityBiography: ZHOU Guofu (1970-), male, Post Doctor, research di-posed of var:TYHC NMH G_To describe the modrection: parallel computing， program semantics and Petri nets.el，Petri net 1s exlclluel. 1l1 uills otcu0n，we only summarizeE- mail:gfzhou@ whu. edu. cn .t To whom correspondence should be addressed. E mail:yxhe@ whu.the extension briefly. The more information can be found inedu. cnRefs. [1-3].Wuhan Uniyergi数gnal of Natural Sciences Vol.11 No.2 2006There are two kinds of places : control place and var-iable place. Control place is same as that of PetriM°: S.- > VU{nout); V is a set of typed values andnet9,10]. Variable place is a special extension to Petrinout is NULL;net. The graphic representation of variable place is sameE: T→bool.as that of control place. Token in a variable place is de-noted by the value instead of symbol‘●’, and the num-2 Processber of tokens in a variable place is the current value ofvariable place. Accordingly, there are four kinds of arcs:Vx∈So，r(x)={t| (x, t)∈R}, w(x)={t| (x,control arc represents the relation of control( flow) whicht)∈W), r(x) and w(x) are read-extension and write-denotes the firing of transition will consume the resource;extension of x respectively. .read arc represents read relation which denotes the firingVt∈T, r(t)={v| (v, t)∈R}，w(t)={0| (v, t)of transition will read the current value of place but not∈W}, r(t) and w(t) are read- extension and write exten-modify the current value of place; write arc representssion of t respectively. v(t)= r(t)∪w(t) is called V-ex-write relation which denotes the firing of transition willtension of t.modify the current value of place; read-write arc repre-The directed net-3] N= (B, E; F) is a general oc-sents read-write relation which is the combination of acurrence net， if which satisfies the condition F+∩read relation and a write relation. Another extension is(F-1)+=0, where,the semantics of transitions, i. e. variable transition isF+= F∪F°F∪F°F°F∪..，presented additionally. Contrast to variable transition,F1={(x,y)| (y,x)∈F},transition defined in Petri net is called control transition.( F-1)+= F-∪F-°F→∪Control guard determines the firing of control transition.F-1.F-1.F-U..The structure of variable transition is composed of three“。”is a symbol of relation composition.parts: E denotes a control guard- which is same as theA general occurrence net N = (B, E; F), ifx, y .control guard of control transition; B is called variable∈Eorx, y∈B(x≠y), and(x, y)∈F+ , then there isguard which denotes the condition satisfied by variablesa partial order relation between x and y, denoted as x . <( places); A denotes the actionE5.11] .y, or xp(x,y)=Where, Sp is a control place set; S。 is a variable (x),p(y))∈F,place set; R and W are read and write relation sets re-Let N=(B,E,F -{(x,y)}),spectively; F is a flow relation set.ρ(x)∈S。N(p(x),p(y))∈R→(p(x),p(y))∈W-4-tupleS= (N, C, I, M,) isa net system, iffRA' x≠βA7 x1→p(b)∈S。A VeEb":(p(b)，expression;p(e))6中国煤化工A: T→L; A describes the action detail of variable36'∈lTHCNMHG:r(p(b))- w(p())Atransition; L is the UNITY statement.④M is the marking functionof N, M = MP∪M°④V6h ,b2∈B:p(b),p(b2)∈S。\p(b)=p(b2)=→UE; Mo is the initial marking, and MP: S,→N; N=br | 1≤i< n};Petri nets. Consequentially, Net system describes theInitial markings Mo: E(t;) = {false|1≤i V;+1; A (t;) = U;,V;+1= V;+1,7;;en by shared variables ( places)，resources and relations.This statement[8] denotes that U; exchanges the valueMoreover, the dynamic semantics described by process .with V:+1;can also construct a net. Obviously, the system specifica-In Fig. 3，the firing of a transition may reduce thetion and the dynamic semantics are consistent. Accord-number of descending arrays of M(v;)(1≤i≤n)ingly, the theory techniques of Petri nets can be appliedWhen the marking satisfies Vv;AS。 Ai≠n: M(v;)≤in net system. Our next work is to study how to use theM(v;+1), then Vt,∈T: B(t;) = falseAE(t) = true,process tools of Petri net in net system.i. e. t; compares the current value of v;(M(v;)= xh) andthat of V:+1(M(v;+1)= x;). If the current value of V; isReferencesbigger than that of V;+1, then v; exchanges the currentvalue with V;+1. Consequently, E(t;) is true and B(t;) is[1] Zhou Guofu. A Method of Softare Architecture Based onfalse. When every E(t;) is true and B(t;) is false respec-UmiNet [D]. Beijing: Beijing University, 2003 (Ch)..2] James L P. Petri Net Theory and the Mocdeling of Systemtively, the sort arrives at the fixpoint and terminates.[M]. New York: Prentice Hall, 1981._3] Yuan C. Petri Nets Theory [M]. Beiing: Publishing Houseof Electronics Industry, 1998(Ch).4] Pelz E. Place/ Transition Systems: Concurrent Behaviourand Logic [R/OL]/ [2004-12- 10]. http://www. infor-Fig. 3 Sort specificationmatik. uni hamburg. de/ TGI/ pmbib/ p/ pelz_ e6. html[5] Chandy M K, Misra J. Parallel Program Design: A Foun-In systemE, letn= 4, S,= {y， 的，的3，v}，T。dation [M]. Boston: Addison Wesley, 1989.= {t, t2, ts}, C(u;) = Integer and the initial markings[6] Jensen K. Coloured Petri Nets: A High Level Language forSystem Design and Analysis [J]. Lecture Notes on Com puterof v; and t; are: M。(y) = 4, M。(v2) = 2, M(z}) =Science, 1989 ,483 :342-416.3, M。(u) = 1, M6(t;) = false. Based on the mapping_7] Christensen S，Hansen N D. Coloured Petri Nets Extendedrules, all labels in process must be inS。and T. So, wewith Place Capacities， Test Arcs and Inhibitor Arcs [M].can get a process of system S (Fig. 4). This process de-Lecture Notes in Computer Science，, 1993,691:186-205.scribes the sort procedure from4, 2, 3, 1 tol, 2, 3, 4.[8] Lakos C. From Coloured Petri Nets to Object Petri Nets[J]. Lecture Notes on Computer Science， 1995 , 935 : 278-[9] Dijkstra E W. A Disscipline of Programming [M]. NewYork: Prentice Hall, 1976.+@20--010] Bakker J, Vink E. Control Florw Semantics [M]. CambridgeMA: the MIT Press, 1996.[11] YuanC, Qu W. UNITY and Its Missing Structure [C]//Proceedings of the 3n Workshop on Adrxanced Parallel Pro--0-cessins Terhnn/qries_ Reiino. Prblishing House of Electron-中国煤化工fYHCNMHG]Fig.4 Sort process354ZHOU Guofu et al :Process of Petri Nets Extension