Skip to main content

Full text of "mit :: lcs :: tr :: MIT-LCS-TR-170"

See other formats



Frederick Curtis Furtek 

December 1976 

This research was prepared with the support of the National 
Science Foundation under Grant DCR74-21822. 

Massachusetts Institute of Technology 

Laboratory for Computer Science 

(Formerly Project MAC) 
Cambridge Massachusetts 02139 


Frederick Curt* rurteJt 

Submitted to th« Department of Electrical U0m* mA Qmqvm tomim m jtif *• ** ** 
partial folftamont of the r oo alnm i m far the Degree of Docter of Mitetupt . y . 

We present a theory about the logical relationships associated with system behavior. The 
rates governing the behavior of a system are expressed bt a Pep net A sot of assumptions about 
the modelling; of a system permit us to separate system behavior into two components, what we 
refer to as information and ggrjgg l oform s ttai * c oiws ro o d with cbjtejt. and how they an 
rjsojyjd. CotititfteeMtcejtieiwlmth^ 
are njgeojstojQi or choices. 

We develop a concept of information that to nenprobaWllstk. It is not inconsistent with 
Shannon's approach, but simply proseads from a more bask idea: It deals with possibilities, rather 
than probs^ffltim. Our approach e m bo dies four common notions about information: (1) 
information distinguishes between alternatives; (*> it roteNes choices; (3) it is transmitted and 
transformed wlthm a syitem;<4) it mm 

something about future behavior (pr s rl i rM o n X Wo can identify mom points at which information 
either onters or temves a system, and we can trace teformtlten u n flowa tiirough a system. 

The control component of system behavior is de te rmin e d by a system's control structure. 
which to Mover* jra^ 
lnterprt^ s^hTiyg, tc^d^ T rmintw d rtL <« «*-**v< ? w .<v^ . - F*~ 

When considered separately, die theories of information and control are of limited 
applicability. When brought together, they provide a t o ahnteu e for predicting and postdkting 

Thesis Supervisor: SuhasS.Patil 

Title: Associate Prof ester of ElectrfcaJ Etigineiilng and Compute 

I with to thank the foHowtaf for their comments and sugfestion* Aoatol Host, Suhai Part!, 
Ron Rivest, Robert GaHager, Mike Hack, and Frad Commontr. I atoo wish to thank Kkn Lewis 
for her perseverance in generating the text of this thesis, and Hannah Allen Ahtoott for her help 
in labelling the figures. 


This research was prepared with the support of the National Science 
Foundation under Grant DCR7 4-2 1822. 



LL Spurn Models. 5 

L2. Petri Nets. *u.'.Xr» 6 

13. "The Problem. « S 

11 Outttnc of the Thesis... 14 

lllBlllll<-'-v:-*wl«! , 

21 Nets. 29 

2&'Pettt'N0tS. . i . . .yVifW*..-..* •«4^'i^*^««'^*iyt&l^.^4JM^^l|«n>*-V:i.>^«|'«V*» *■♦•:* .'•"j-'-W 

23. The Simulation Rate. SB 


1L Assumptions. 99 

12. A System. 40 

19. The Puis. 49 

14. The Comiot Structure. . 48 

11 The Modes. 59 

16. An htttteMasd System. 99 

17. ExaiMloi of faritteMMO Swomm. 97 

4J. Information Gomsnt 75 

I T lufw mMm FTow St 

41 Resotvtng Choice. 90 

4.4. Resotvmg Conflict «.,.»,... . 92 


5A Event Graphs. KM 

12. Paths. 102 

51 Cones. . . 119 

14. System Space. 129 

11 System Time. 129 


6J. Information end Control ....... 145 

6.2. Transactions. 145 

61 Extendible Stroubttom. 151 

6.4. Predtctien Graphs and Pestdfctton Crapfcs. 159 


71 Evaluation. . . 170 

7.2. Putttri Wort 171 

References. 179 

Index 175 

--•_■*•" &-— t > »"* ^.'"rf'jl-t- „V 



l in vm 

nut vital 

rutat m* mtfy tiwpwrtn y 

Soom of the mora 

it atop, 
it tiMt oif^rtv. 

: W^P »^PPPWW ^^Hi ^^Kt^9mm J 


I hf Ha * V a aaa|pjt «T taa 

(«Mm tho ioiMMilojr 

ratting tymai tank aad mm of ftow (tht «mM of *|OMai 


, • -, « "<,- ^ 

wp0W ^B 0OW0I0J ^HflOO 

(c) a aot of difftronot 


(d) a description la ptatn Enftwi 

Bach of thoN ha# » d^»min to whidi tt ta i^tto^ «l»al Tat tfoo of modal wo* bo worfcftnf 
with It MfMdalty appropriate for than iptemt in wfck* tht taOBtBfeB. Mi SaMfiGMtiffl. fit 
ini»w¥i^i^un an bw bub aian^a^. 

• *Modof it otad n two tMafcJljF d»lofoiit^io)iioii ftow^Kor .la a 
a particular tyjtojn* or to a goatral Mt of ratts aopacaMi to a 
dtfftroattal aquations rotating tht ottctrtc and fnagnitic fttM 
li aw tMkii pai affi 
tha distinction It Important, ooaaatt wW make dtar tht 

L2. Petri Net* 

Petri nju are * d*» of system mode*. Ute the ftrtf three types of models mentioned above. 
Petri nets art fjQ^ motets, and they permit mathematkal anaiysU of lystem behavior. However, 
unlike a set of differential equatkms, Petri nets art discrete, and only flntory methods an 
employed. Unlike finite-state macMnes, Petri nets makt no attempt to describe a «y*fm tn terms of 
a total, ansmicttjrad, system slate. «- -*r- l frT ,t ftm «tt 1 eWfrllg TTT FTT « which 

machines, they ntam a* 4* repfesenitfMp^ the ability to 

express ahernathws. , In relation It. thtmedcior^Btem^ ofi-fport 

primitive concepu and, therefore, permit a more f«iesi4 aod p9«NRtMt theory. 

A Peal net is simply a bipartite, directed graph wheat vertices are catted states and events. 
(The term condition is I nt er chan geable with 'state*.) In the graphical re p resen t a tio n of a hat, states 
are drawn u dixies sjkI events u rectsjtgk*. An example is given In Figure LL* 

1 In Paste net examples, we shaU adopt- die cenvstutea pTaMte^fevkiwarcaM tetters to states and 
numocrs id events. ....... 

We say that state i is a pjspjnjjgfcjiof Event * ifnd only tf ttww b an ire leading fronw to *. 
Simitarty, State jr is a poMjenidjMon of Event « if and only if there is an arc lading rom * to *. 
Thus, in our exempts, »et« ft and S art tht pmomUtkim of Event J, while nates < and # are the 

Before we can use a net to sntertats system behavior, we most fir* Intttelto It This U done 
by desi gnatin g certain «b«b at jnjgal cojjg&ent Tlnm%s*e*oJsn1n%i§ are shewn graphically 
by placing a token' on them: 

Flgorel«t An Initialised Petri Net 

The 'firing nitr 1 for Petri nets statei simply Mat when oath p ie e O rtaiUm i of art event hohto 
(contains a token) then that evert nay geoi (fire). The occorroiKt terminate a WoMing of 
(removes a token from) each pr econ di tion and initiMtiia a holding of (places a token on) each 
p otte on dltlon , Nettee that this is a strtoHy fatal operation tetolvmg only the evom and its 
preconditions and pMtcon d ahms . h general, there may Iw nmral e va «» occ u rr lM liKJepefKle^ 

'■ ekJSMst -^MShoe^MsMMMM^anW' '■ 

ww pjoai£rjoja. 

-i *yj„',uSf>4jr#*3^,k-..-<- „-.**s*- ■ 

; -XNS-. *f t i fRPSW<!9VM liJ?M^f%rfSi^lP^y|^i!flf^ iffnj* ere concunemry 
W^l* <tHi|f^Wcpnd|ttop hold) but they havt « conwoa BimmmM^Hwi v%jnf tbifcthe two 

and. therefore, ttM occurrence of tutor event will <U«bk »h« otlwr. In Fifure L2,£wto,/ «i»d 2 

^*P$^0$§m6M£M£mkpWtofr nn ti jmmit<im4 mmemm awb» fuydMUiig yet 

another Mt of holdings. It should be apparent that Acre are, In laaefaj many ahei aei^t 
limutationt of a net (and thai; In general, that ^^limiil^eiitf^toiKmdediiidefliiitel^L 

1*. The Probton; 

For the dejignejiatid mm of complex »y»tcmi and f or the participants in such mtmi the 
boh; of the day-to-day problem* «re baity to be<efe*r^ tto f<*owiag torts of 

(1) Under what conditions win* attain pattern of behavior be produced? 

(2) What are the consequences of a decMea within the system? 
(S) What are the effects of a system modification? 

ffl How donhehantpr in one.pejiof tto tye^jaflhanri balaeier in^anosher part? 

■ a#W*" •VwWpwW* f 

' •"■ •-.■'--.' : ':- --.V :■ u:..:. ■: . - * r.*' . C- - , *■.>■> U . / ." .- : >V^, very little ttttntta« h« bt«a p«M to ttostwpj.^ pmitom, jjnn heft» to teoaunt 

for'th^.^her mm#mmim*m»mmM!mjm*mmK-- -* 

Tfc, p_> i. -^-~. rrm p u 1<|T||i(( g lid „ l|MJi fn| lllli>)ilMft f^pmi r\ 

; - 

' rtln Mtt W DOBfl CnQSOR Of aM tytMin ieprOieaBmM< ^tmpiuewnv SO wWUf 'WlSWettWeW^W*; w» 

find a way of determining Hit coaoaaJnts that a Mt pawed on tkt o ct wr onco t of a- purtioutar 
subMC of events. If w view the system as siiwiatif mlems ( ■ m o ntfUO -a w^H oai i w wt, then those 
events can do urtsrproBsfl m lying on too systsmronvironmant oouuoaoy. 

, — a- -□ — a- 

i i 

1 Syetam | ^virttfiaant 


1 .Q □- -QU - - 

Wv«nt lying on tbe boundary 

In this way wo can arrive at a chvacterttttton of tlw external behavior of the system - a 
characterisation that is independent of the perttaner flmhtflfrr by **** that behavior it 
trnptamenttd. Defining tht external behavior of a system at a Mt of constraints on tht boundary 

-'■ v/- ..■ * .■.^•-- -, -■ •■ .. .■^■. .-.■(„***;;■ J-$j*V. . iff : ,■/■ - ? ,: ./. - - ■'5y'A.r' i l - - j/. -. ^-;. *#•" S {3 ■- - ? * ' -.; ■-■* ■ ■■■ 

events roprtionti an attempt to got away from tht i » <i i ciiv notion of txtojnal behavior at a 

function from 'inputs' to 'outputs'. 

Then is, of count, a way of answering any outinw whjltntvor about tht behavior of a 
(bounded) system: exhaustlvt limuktton. This involves cataloging all tht different patterns of 
behavior. For very simple systems this is a practical approach and is, in fact, tht usual approach. 
However, it becomes pamfuHy char that thU method ncEtremsty i mpra ctica l for anything but the 
most ehmontary systems. A more dstuablt approach would bt one that afMtwored ojuasttons about 


iiprciiffititlpi. ■ ■ ■■?■: 

Reduced to its staple* towns, tt wet tbie we nadc to ho »i)Ja tt> sj m rnrini how one choke 
influenced another, to a Petri net, a choice it re pre se nt ed by a shared state. For our Durpotes, we 

cm ditdngyjtft between two gmi of dwiOR fjM cMn 111A oaMt^Md ckoj^ 

' v , ... -. ,_'■'"•*"' ... ..... r*"'!., .' . f™"'i 

(a) Example of Fr«« qHbico (b) Exowple of Conetrained Choice 


In the first cue, the net in no way specifies how die choice is to be resolved, and thU U how 

.1. . ' .«■ *m. jK^v - i * "" : £- ' 

conflict or nondeterminecr. it re pre se nt e d . In die Moand case, a hoWtnf of die shared state is 

■"*-r:v .. -., * « • , "''^s^i^^^ •- - "*; 

paired with t holding of one of the two outskk inuw to resorts the choke. Dopondinf on whether 

.o- ..;.;, "•:; •■ r^ - , ^ % • * *« sir , s . ,* . f-r* - *<?- 

the left or right hand state 'receive! a token', either the left or right hand event will Yire\ (We 
preclude the ate where both outside stales may bold con cur rootty .) Nets containing onb/ free 
choices are, naturally enough, known u fret-choke Petri nets. They are very amenable to analysis 
and their properties are weB understood. This is became, to a fr ee c ho i ce net, no choice influences 
any other. As might be expected, f r ee choke nets were net general enough for our purposes. We 

■■•■-- - ■ ■ ■' - ~ » . :~w\. ff... i -.-- 

needed constrained choices. 

At a constrained choke, now a decision is resetted win depend upon some previous pattern 


of decisi on s at tfeifree eholeai infl otliir rimdiiliteri rfiitrai Thi nrtiMBtti imi to tfaittiillrif thli 

deoendencv. TtM situation was snOrt vemebaued hi the fit!/ mm wt had to^dftttnJoteh between 

'•'■ raMAliil'iteariMu at ftMiMMtiitiiei. TIm unh heM ntoiBifOri in lie In dlsciitorlne: The iaochanlirn 

Opjy "HWI HII ^0O^SWwa^0> 10V v^s*p^B*s^Eue^n^Bv 1 IWn wj*sj*|SV feVO^v^Bj^Sv W OtVW^wSVPTfw* 

■ - "iJ^grts^anin^iW^ dfll^a^ . 

and there «nu no way of adMvMf ewfoau using iimonttfttf Mtfc So we had to find m sotof 

restrictions that permitted us to tract the flew of 'influences' white stM maintaining generosity. 

- Turing nwxMrM had shewn that • model coeld be OKemfc p o moa t o* without jpdjctwg its 

L4. _ 

Petri iwtt originated with the work of Ctrl Adam Petri who pubtohed tte awninal paper 
Kommuniiatton rait A u to m ato n in M62. The model introduced there was later refined by Anatoi 
Holt DOX and the modified structures wen given the name "Petri nets'. With Holt's work there has 
been a steadily increasing Interest in nets* the key attraction being then* ability to represent both 

Unrestricted nets have come to be recognised at an ORtremsiy general, syoMuov model But 
because unrestricted nets are inathometicam; intractable, dot approach has boon to study restricted 

ctei s ei of nets. If we eliminate either concurrency or chotee, the problem becomes quite 

State machines air* daw of note In which behevkr te steittf jeeoentteJ - chore U no 
(juntui lency. m one form orrunoiuer, swjrnwjcranm^novwoeoB'Oiwuno'rOFmany yea*i> invyvv 


been studied quite wu o n i ivt ty end a gnat 4«al it Jaowi about tbetr properties. State machines 
will be mud In oar theory to provide a natfcm of 'sJaaaoiiionoii'. „ 

. ivm wp j TPa» |Pf^nF7ajeBan3< en .js apeejaBajvi pp.^,|paaB|pf>aajpp^fffjp|pwffpo - ; ;t,. .- . -..* ^ ; 

£9Js£2SL WbQBSk W Mow* «m«U v* iaf^w'' llw||BllillWi • Wy ^^bt|W»> e^^f^lf^wJIlVy - 9JVVtr wVonvtW^tW ls#«w»^l*» 

r ' 

Although they've not been studied a^a^ojtejiiiof^ 

watt utiderstaod EL -.4* ^ 1&.JSL Tlte-nwM Bea^tecaaMananenfent.a^nuuFfcad 1 eranii is that it can 

describe: uahr » feted. aeaoBltinB^aeananMwl, aelMwka& JMaSi 4eaJMb«iMeHJeMUa.aae of Jade- fact in 

our theory. . ■•.„ - ._ *,-s: ; -',Y4' - ■ '"»."'.*-„- 

Fr ee- d aaeca neti art a seaavaaBaiawr oT botifc^jotie aaaddaaa >and ^fiiarkad ajaphs. They 
oermit both conc ur renc y and cheese. Seme shtttift&tnt leton* hew been obtained EL SL but. as wo 

■*** ••*•• wF^w*ae ww»w»iM i wtiii i wme w*»w^^owwp» a^wpa*wei enfin eweou* ■ # wae^waaef aaoa»w» wwwti wppo^ppj ^wsT *o^pjjjwb> ?t^^_ : ww ^ 

mentioned in the preceding section, the e ac hi i i en of onastreJnod c h oic e s mtrictt generality. 

An even larger dots than fr os eho t cs nets art dw ib msi nets. The mathematical analysis of 
this cam of nets is considerably more dtffkut than far fras choi c e nets. Only a fW results have 
been obtained & m Patift resut 091 is rigmftetnt since It shews that in spite of their power, 
shnole nets are stW not coftudeedv ewwral, There at a duns of conrdewjion oroblirns that thav 

^^•••n*** wvmwm ww . emewe wow** wmooawaKwoRewswv .. aaasopwaaaawt ■ •.aaaaa-wa .ajar av>: wjPBeoweo; . weu/ . ejeaMRKWMweoeuePtn* . new wnwFaapwoeap- ■■■■•' ■■•■■•.sj 

CaUinot fnodcL 

In working with thto hierarchy of net sobdusn tt Iwcamt tocreutngty dear that the key to 
the problem was the abitty to trace die propagation of 'influences' within a net Over a period of 
time, the 'propagation of influences* began to leak iwipicloaily like the flow of hrform atta n. This 
was an area in which Petrt t», 80, tL 2fl and Hek H, K HI had developed many ideas. Their 
major points may be summarized as foHews: 

(1) Informatitw U<or *t tanat ought to be) a tysta ai r< a Ulw concept ^, % ,i r ^. 

\*»r a"t^ va»?jOBBaj»a^eoi lev .aurootaV lfa^w v f|w7wap'^|^ppalB^w» • \aV^rJ^^R.d» y^^^^^^K^^m pa^aw» eHw i^wwl •Jv«a»'aw9« a ^la^wW ■»/ 


*» 1 


(S) lnronmatan to ataH W ,*r **••». ft fl >i M>u i m ^»# > H w w » Y a maaii oonnkt* 
(i w nde tar mtn acy whoa Hit system is tmaUmwi to be rennJnf forwards in time.) The 

(4) Information Is tag by a system at tliost paints wham there "is > ■'toOmmmtimee 
(noiid o ai nonacy whoa iht systsm Is con i td a r a d to bt ronntng backwards In tone). Two 
information toot In a conflict s itu at io n specified bow to back op one stop. 

ns^Ne> Kl^V a^Pve^Beooe^o^B HW eewe ^meveaWe^eol l^WeaHl e^ej Wo^PW oaol ee ^eWsw • ^W*.vHeoleaPB^PMee^^-i-^ew^^wJ^r^^bwn^^^wm^n^ 

behavior. Ha and Commoner m n M t w s fu l H up p lyttj tha hka to itate machtaos D31 Within 
the context of a statt macho* they wwf aWs ^ 'id pi Pf'^fbib^W^ jyiiiiio^' and traca their 
hJttories. The theory irtojie^Mtw^aJfl^ m stajnif Hsnot of Ibis 

wont it tnat n onaonsnaa war prowspw natrawannBaow oaom amsatwnioeM ap« wf^mmw^mww 
concept and -tty~'ittdfc^^^ *©*• 

neTorimuiori flow to a ihoa» Mt^ sjs^ > sj o j sjwsj» oMnt 

• Out -of tboaa asi towgnmnt t hrn a eJ 

i'i^aafflfc' -^^/M&di^^^J9&&jL ^^^1 Maaa^fc^adhYT *nyinasr iaa o^h^^^s^emobnY^iaola^fc^ih^^ttl^sa^^f^efr a^lanl Jamo^bVMflaol^hlotol I 
^•W Hm^S^O o^& ■»e^ SHBCsHt fh» e*W^swa^i^B^WnW^Bnen^r^Bon1^Rv^^b^P F ' ^» "3F..^yf*^fl5HHS?^r 

chokas art resolved. The dtotrot ewnp e a s nt Hat to dfr w at r a* ?teo» ropstttivo - aspoaa of 
behavior Ihnat aaeetts nenvsiteaOnffetsaff bfhew dkOlaaaaftlliMkt^^HtfMl^laitJF fooofnlsod 

■swpfOO»w swooa oeeesape ejBjBos^atasea? miBaeepwisj^F''wswosjeoo^neawmo ww ooopw- onwenmsmnrasa^v wwmwnr^ppaBo^"WmeeeowswmaeJipv'-^^^«jr:;, »v^ ^^^»w»»» *-.■ 
,y i tf 'i M .j; -±t$!± j£ -^ m a:J '■■■-■■■*« & itL^i **';&. «&&&*£■.*• j-j-i.-. - '-^Mf/i f tyar\ fiffriiiiai^iinilif jtk isjsVr^Y^nrfni^tfi'i , f ^^^A^^^^i»-f^^ o^ B fy'g*^e^aoinarMSMl 

ntt mm f or iwiKHH tfemweWKOiifc^j^^ 

anw no^ o*"^^w e^^noanppoww^oe'^^oowwo ^e^ne^MeaH^w awi iw^'o^^n ™ eo^^ * 

■ I.:.' . .^"i i -.I. : "-' v : ; v ■ j.-'^'Vti*:.",-'; a . ;, 7 , ?!>■ .■ :., ; ■■':-■; \ ■ ■ , ~ ■ '.«*-^ ,: ?-'-*-' ; ;. ** l' 7^?r-?^' *"i**; « « ' : V* ■ -* '* * *■■ n ; ■■ ? '- : '- ■- -;". ^-V '' ■' . ■■-■"■'"■■> 

* Hob and Oorafnonar , i wort actoaJy daab onta wtb postdMbw. Howoaar, abhotnh K*s net 
m o ntto nad in tha paper, there is a deal not la tha thearj daeanf wtth p nj dtct ta n . 


Private oomnMmicatton 


Ho* has continued Mi work i« the*** of ooav** fcft too oufy to say how our approach 


relates to Ms 01001 tot mn Owory &4) H ^ Jn * fmmto* m* *** *» body «* 

Th€b»*te»mictu«w1|W W «dUii fI ^k«lWAflol UU|«t*Wp.rtit«.dtrfct«dgr»ph. 
A fogi nfi. te a oot to which ,. m ottach ,* y*& frmpmim ** f<* whs* we dofjno o 
'simulation rutf. A MUttUh. (*m onon^ « i^net io whicli 0Mh^Z«l Mu «t»ol]r one 
taddont ore and cm emergent are. An fXoHgja^ioo^^jfopli)^^ P«tH oo: to which each 
s&£ h" «x*rty «* iitdd«nt «f< and one aw uf w O. ^w. A state ja«imon«A t of a Petri wt * a 
oMHhfrapli subnet m »Mc* •« am conneo* to a ,,»/tt^^ front 

oonojgnoM of o Pott net it on evort-gropft subnet io wb** all s * i c a nn o n ed to tfuutkifwting 
mrent on uMd. APortM covered by note wmoonsntt (oxot rm^mmU)U said* be^as- 
tr§£h <1y9fTf^^ (laaiaa^ ^MPMlBteJi)- :M^»ioi»?*M>!t £»♦ J^ : f»f>Ai fhjthjfGp .and 

*P" ' ^■'^^"^WWfl flO*"^;,,. W^p -^ .mijw- *»»*«$ ^^ppa^p^^i^OOjavOWr >OPj^^0^a^n0^pjW %MSU9npUOa«AjP6*v 

Tho UooJoHbL a kfo a n » t o Mt of paitfcJ rr'nMtJfftMlul .#«*>• MWlf ,* sw&la 
tfjagan. among a tit of o**4nm1ieft fM «w«sagaB* s t|Pf **§ fow way*,** w^ two 
*"«»nces (holdings or occurrences) x and y may bo relate* ^MuLyraajr bj Jgniftn^^ *&• «"»• 
instance), x may precede y, x may fottow y, and x and y may be concurrent We show that In a 
simulation, the Instances associated w*h a Mnrf stati tonunoio* form ^ 

■*^^*mm>?' -A>mwmfts*®*«**^ 

Chapter* Ojstomt 

Seme baste amtnnfrtons «bo«t »# modtHlnf of t iy^ >f« p . ^i.l. a. Tt— em nonitowrt 
mhb me tonowa^ approicn. 

A swtem to to defined as a Petri nst - tN svjsaa Mf^ tojsther with (I) a sot -of ettbosti of 
states and (2) a Mt of stibssts of events. With tM help of five axiom (r**m$mr seswopttoiu). 
we're able to establish aN the feeturoi of our mod* Tht stibssts of states an mod to gantrato a 
covering of l-token' Matt components, the parti of the system. The wbeeti of events are used to 
genera* a covering of event components, the modes. «* liewoito* fl*paro*fe jaojl itructuret 
aseodatod Kith strtedy ssouonnst behavior. Tht mooes atefjojalotwaoroi modeled wkh asoil 
state behavior. The modes may be vbjiod ai the'haiMeJ fi i fiiii i i i f ofithooyotom. 

To eattaet the control <*me«noM of syitem behavior, »• ftrstfensrato the ttnasfiZlQaUifi 
of the system. This to done of ' c sMap i mg' oech oNbe p«*. T1i*aln»tiativ»dBis» the 

Mates and events of the system net. Themamtwe*yfNe of sh o m ol ivs dusts: those that contain 
just stales - they're caned Mi • and these that contain JOst events - they'w cafled ■] ajtjwi The 
alternative dassss induce a e^etssnt net that teaneeeftt ftapk, Thhtto tM offi^ tfpjfflfo of the 
system. The msotings fossa the events of thoenntsoi neamno, <rhrtethe tt»U form the stafnv As 
with any quotient system, the control tfructttie losss certain fsaturarof the oria^nei system. What't 
tost to jnstthentdity toananjnmnotn^ <* 

the system net), there to a corresponding control amnjflg ( i fcw n ^wi of the conn* structure), and 
the two HiiajhmHlii u« Isom o rph ic Tbe snmiid i toi u b nvm ^^^ Urn fit* by replacing 

each instance of an element with an instance of the altomattv e daw to which thai itauaui bitenfi. 

Distinguishing between akernativei to the domain of Information. Thafs the topic of 

■^^^^sn^i-^v^^i^i^is^-^*^^, ft--- ■- -J.;** n, „ 

Chapter 4, and in that chapter mo(k» ytof > f > u w ll B WWt»l role. We note here an important 
property of eaado* wi »e<i mmm m fmm&MJ +imtlMkmmL^ » direct 
mult of this, each mode it to o m or p l ik to At central ttrvctura. aoeV Mtofff eea, Ihe no4ea,-#ro 
iwawtophto to eadi other, nto^eaw *ata e » a » , noleao N »tow > d^ #n loto irwu oo itlm i of 

ThO OBOJBOl 0»Mto« p»Oi^*#OWi^ 

^■runpond' <ht lirfuiMtofJl m99 nm 9t mmtm^m II|JJ»J» I J hoi^to a «io >U > w^e 

ifttrodtlCt the ip a.,w ra o^ 

f^» »i ,. j-. ^. r ^ _ n| | ^ jhhjugwej titoioj Hon (In nut 

comain d* .iimemX No t~ fctttoct) ontotO otoaiotoeltol.ietoM i» MI an ha^ too tame to no» » oro«» »im«.h ■■ T l uri) IJ n i O f ii i by «f^^ two «h«ef»: 
«) the atojSf^^hM «• wMd. « hH ja gml - toJatotoj|| W mm " * cotor 

' <*htoHftjitoi*»^^ to Uetoi aodnopl ic 111 lehew' m ihi unniul 

•tfdetoro. By de fl wlw a, o pp t lej n lol o l oan eoooforatoitoat^ooeli owoataf, onweao rec apto w th« 
'iihipuni Behavior of the sjoam. - ^ l2 . v , . 

<*» pecuaar ~y of d**^ tt«tontapt of Inf otlmi oaftoff *>«!**»«; ui » Wtortat. 

information «*h «to > ii nojo^ >ot*hojpjh^^ * the 

^no 'OaMwatoa'OnMosona ofTt^avjei/'ao^o^ 

y{'>':--i% vjs. 



Certain choicm will mveive cpnfj k L which, in oar cast* U •ojiivatont to free choke. We define the 
i nformation yarn of an event to be the information content of the event mlnui the combined 
information content of the event's oncondtttonv (The information content of an event will always 
contain the information contents of itt precondition* end po o aondt tio n i). The Mefjnayoyy fcjft of 
an event is defined to be the information content of the event mimu the combined information 
ootitem of the event*! poj|cen^^ 

The tefoiinatlon ob of » eveiit « to en^ 
conflict with *. 

The tafermstton jo* of an event « to the set of iwadei covering those events Ito f^vnjflda 
conflict with #. 

this means that btfomwtton it gatojei by a system at >fHm*9*+miim +*** 
fjsward. conflict, and to fcnfbrajfnomat nrectoefc/ ilmei pinto » hi» the* to hagwonft * 
Furthermore, the inferinttoei gained or hat fn t cwtfto sto ma* to enervate** to modf vtoaj how 
the choice to resoheo. The stmt mm of Ideat i^m mwmM Mm mm* ■+» #" 
information to resolve the choice to inpoltod by the svitom 

- 1 5^>>;;^.ji?'4':jft^ 

The control component of ivstsm behavkf te snttoeh; determined by tht control structure. 
Sine* th« control strueafte it an event graph, the tsjsaff/ef-esnj^is tht ttwavj of event graphs. 
Wt should mention that virtual aU of our resufa pertain * event graphs covered by bask 
cte&(ekmen*arr draito omtsining e*s«ilf «ie witen). Thn n net a BMtedon for us since tho 
imafos of the system parts wtthm tht control ttnid«nfom» a oovwax of bask circuits. 

We begin by ^ ba ^ki g the c^ wtufs of stem a^%nuJilon i,' " We then show an 
Important r»buk>iuWp betw ee n the paths in an eve* be paths hi a correeporidteg 

Unwtattsenl Thfc pernttt ui to expost tht sytmn* v 

ft is an 

f 1 Utht* < tti 

fltothss'tfi ooainme of ^ fo is na^ ft 

(Note that because we're dealing with event graphs covered by bask circuits, all instances of the 
ra mi i » i nt wiatal»oidefedJ ThtvolntotAmjh^^ 
- ^ ■p hlhmwth ^m 
path* huffing the sine wri poh m as » Th« Cnl l n^ l iia gnt i ml i>. N.^ «a#T»*pt to tht tFo j^en 


There exists a path from q x to f s whose 'ImsaV in the event graph is a path with a 
irnchronic detay of k-L 

Remember that a simulation fc a partial order 


. Because synchronic delay it not & convwiiBliCBnMpfelft^MKkv^ifc wo:ird*aduoi;^he;;Op n c op ct 
of Wk com' and 'frant com.' The backcoar ef inmit<liU4v«tpi» h to the set of states j 
such that: tlwjrt dow n* oatott ptfhof deny itro rorffl i ntdnt, atrand w h o os fto* state to *. The 
f rent cont of * to tht set of states < such that; tntre dees net aatot a path of delay uro originating 
it * mnd whose to* state to I, There to > rimpto utottowl i tf b e twe e n synchronic delay and back 
■ltd front cones: ' 

The synchronic delay of a path a (In an event graph) to equal to the number of ttonoi the 
back boundary of *% bjgd. to < 

Tht lyiwhronte delay of a path a toeouet to thtmindwjr cf tunes wtefjeeg boundary of n's 
tail to crossed. 

Condi have an oxttdnthY inenuating onwtoction ■w'the dnnriatiafii of an eveufcrgeueNt. ■- Tho states 
of a particular com ddftno a an-tos of cone-like slfces In oach stimitotson. If It's a back nana, than 
that* cone-like surfaces point forwards, and if it's a front cone, then they point backwards. At the 
tip of each 'cone' to an occurrence of tht i s su e d event For that occurrence, the 'cone' provides a 
boundary between the past and 'not past' -If it's a back com- or tlw future and 'm* future* * if 
Ufa a front tone. Between any two consecutive 'cons*', tnaetfto ^eautdy: om oomrrem* of each event 
System space to assocsatad with tht notion of !s yaclwu a^de<snce vwMch to a t neamre of- the 
• 'flack* between two events. -.- Tlie saithpord c d toj f a nra b aiwoa^two etanto in an eye ejuoh to the 
msntohal token leading on those drcuta containing both sv qui, Whan in event graph to strongly 
connected and fret of blank drcuito ( c lr cu tto without onti-iofcontay M^fi e ^^ * 

metric on -the w 

t Do not confuse synchronic delay and synchronic distance. 


, . .. .-a: > »«,« i.j^.j^^jej^ja^ig^^jij^ij^jj^^^,^^ 


Hi t«Mt 



^^^^P wPJP^ *^^^H?y »^P^* 

cku of tottM Uatfed « 

circuit. Thli ft 



C toBUM MM Ml 

'-■' «"'-' ";■■" t^* » f *:5«p# %: ^<$<|£1$ l 

synchronous cvmt gnpn, wt 

slices strictly atematc Ooohtwcm wNmb tfet mum Mm Am m» «M to ht 

VMMnMM • ■ ^W ^pM**p 9MHM'BvM»W %»™J • 

* «l) m rftsejj.- Wp^i. > l jS0^rt;»»if3 sir," 

AM) tMMt of 



• -r * 'itwioi fc* wi"^ ,« wiw*- ,- -3, 

F rt«sw«o"t ?n«3*f *r>£'h ••.*.: •■■•'*{ 

i3O0 $ '.. 

mm th»tto*wn toMMiililu 




pwwinin; .-mt> 

to Chapter 


■no cm proptrtMi or 
uiufufcr MMNto if tht intom 



Wfchm the oMitml ataaeh*to* there to » mat o rd t n^ am o ng t win Wi tts of the seme 
inttttiig. For each such fttoel oidtrfcigt there to<a esifaBaandmg^4Bori otdtring ■'iB-'ttii'-ijSltni 
wnaanan anwny OBcuninMi oc .- rmi - mm mm|M| v an nmib MMnng. * », - whbhi in* 
afMMPR toinutoaen, the ntoooomenca sjscdttea wtoh MttMng «t to an eorurmiMt of Ivent «, then 

i^mlPJp/omoW pWBW--' ».mo? oaWPnT* BjTggi'Tgg^gMggmggg^^^K f^g ^^^b^^^^K i *jB. • wwP^WWw^'^^^^W ; onwmWeWeMsolBwFoA ■ "'Pbt,.*w. enr'W" L 'oe^B^nnT«WnL-. wP» 

g. In ton* Jan. * will Be onbtr n e gathrt or 

^^^^^K^^> '^^^go^^tsh^^^n atS^^at ^ ^^ 


Wc know that f to an imttnce in somt system 
tlta riw rfi tw chute, tf weal 


lunutotion and that f to associated with the 


patterns of transactions prior to a mm 

The additional knowtodft alews w to identify an ftomnt from among tot ahafnattvei. Thto to 
exactly the same thing that oar notten of tefommtkm centra* dees. So tht 'information contant' of 
the additional knowledge to tejuJvatont eo tha tnfeimetten content of tha rtwn a nt tokntiflad. 
Anything that can ba deduced from ana can be deduct* from the othtr, and vice veree- Of 
course, we can't »y anything about how far tht limutotton containing f aatandt, either forwards or 
backwards, but wa can say that tht patterns of trsamcnoni mutt ba conatota nt with certain 
requirements. Our approach la tht problem U to try la characterise all tha ways In which the 
information associated with q could haw gotten there (p ool dktt o n ) and mJ] the ways in which it 
could have tmanttad f aem them (preaktioa^ feton^ of excluded 

modes. Since information to 'add Wta', wt ew oeat each made m the ntforrnatoon content of f 
separately and than marge the results. 

^■^t^J^^a*.' :-. 


Far oath oyjb j d s d m odi , we know that by tracker ihs sartadhiii hniiieuli ^forwards) we're 
going to generate a sut^ of d» d W , ht lsa faea^em <eat of? * Th* soim* define, a 
partial history of At mimrM wi prlnr M wireo m) t»or la |0 ww al, Uwt ti be araarat such 
eartM histoid fsessibfc. «-«-rr mmtW ttw pamal hae o rtai i w i bs siio ad iidi a^bMiaiily liu, m 
which case, there faty beenia#iB#iaOftdMir «f : |MMf§||I^Nifl|^iHMhifcr-Mt time Wry d sallni 

•wi # into «,ate»% **» |» A nmtwr*+mm*mi t mm*i+Bm* **-—***&* 

pwtW hirtoris* ataxtatej adaVeaeb mM* *A 3te aaas* AiM m Chepwr 3 ten be 
used to 'sitae up' the forward! and backward ptetleiaaa*^ *be*^^ 

and front corns for forward, historic This ii nii • t*m m ot +i*xj n§*mnu '. To 

characterize the set of forward, or backwards partial hktorist, wt mod only describe bow tbt 
appropriate is gra w m may b< «owwo^ lotatair l^dO dd» w«h a auto graph, each 'state* 
c»nas|ioiidliigioa|»rttailarsa|mtm. For * jufllflfca fltt «ad» path i d yni li a M n a ) a»a 'finishing 
state* defines a posslblt backwards partial history. Par a Bfjjgoji m& aacb path originating at a 
'stating state' defines a possiblt forwards partial history, m batb cam. tbt transactions associated 
w*h thm «Vh ,~u u> > pi. .— ^ ^ -i^ mnmritoni " the lonespiinilii^ psiilal liiitui j 

Chapter? Condtukau 
We discuss aspects of the theory and the mthaary. The disco*** of theory Is mainly 

...■/'.-,■_■,:■■■ *' '• - ' <• ' • ' "■ 'i **r* • j$i AS" *w H-"~' • t> «• 

concerned with the future directkw of the ma rh e m t rki in the ana of metetheory, we touch upon 
four related topics: 

<T5g>?o.:,;,y 9f»1 '*? ■:■:*•;■-,■ : : <2tis ":•;;•■ .5 i^'if' 

(I) ' found ^«isJl« *ere a set of 'sttf^idam' axionu for die theory?) 

<S) methodology (How Is the theory to be applied?) 

u\~^ <*^~^ fr-^ma II itii mni| waartfl • . 



2X gefi: 

Nets are tht bttk structural of our theory. 

DtfMttatK .-A-MM 1 an 01*10* ttfrlo of sets «A, 1, C> In which ATI** and CfiAxBUBxA. 
AUB it ttw set of elareonti of N. (N will be » Hw o d at a bipartite, directed graph with 
AUB as tlw vertices and C m the am) 

Notation: In die context of a net structure <A3,C>, we w rite jw y to m e an oe, y»<C For xcAUB, 

Definition: If N U the net <AAC>, then R is a subnet of N, written RfiN, iff R-<A'.B'.C' 

B" c B 
C fi C fXA'xB'U B'xAO 

Property 2 J: A subnet is a net 

Notation: If R to a subnet of tht net <A,B,C> and RwcA'A^O, then, 
for XfiAUB: X R -XD(A'UB') 
forYfiC: Y 1 -Yf1C' 

:- ^?H*^©^^;^-: -^^^fisw^i^^^ir^ffi-' ' 

The ratal fovernJnf the tehavior tf<«r*i«i»«i« «*pr<«Md *» Mm* * * **■* Mt 

Definition: A Petri mt to t tut <S JLF> where. 

SU« finite nonempty <et of «alo» 

Eli a f taiite nonamotv aat pf evanti 

• WP HPW# "^^^J^g^^^^^P^^WPJJ 

;■' ,-'* > .:-''- [ *.?'■■■"■ ;■';'■ -■ ■.-'■L*"i >'■':' ■ ■ ' "'■' . ...::■ 

If MS, then the etements of °> are called the tamt evento of s, and the dements of a* 
thtajspjrtjvejjtof *. IT eel, then the w— haw of a are catted the Input itataa. or 

, . i- fMMMarfOaPlOL dtMhM wA taiH >j|M^aM4if-JfueaMiaikkHlMiiaMaMpAMMi^eiifcMiiiae'M'<. 

Definition: An frtftjaHjod PfgLfflt. to a puadniph ^ I, F, I> whew, 

•■■■ <S. €, F> to a P e tit war . ^ :*•# .-•-''" <*,*■> M^-vy «^ ,* ■<:.. ■?.-..? 


Definition: A state grap h fata* machine) k a Petri eat *JLP> ai which. 
'Each event haa exactly one pracoodWeji and one | 

Definition: An event graph (marked graph) la a Pert aet AJLF> aa wfcteh. 
VteS: TH-Pl-I 
Inch itate hat exact* one input event and one ettpwt event' 


(a) A State Graph 

(IbV ''■%&" WN^z4XNBto. 

Figure 2*1 

Sines Hi a Matt graph and an event graph one type of node Has exactly em inddent arc and 

one emergent arc, it becomes superfluous in the graphical representation to expNdth; show that 

^type of i»odfc Wt ttieteTore adapt an ab brevi a te* l ep f tie ntatk m in whkn eft*y the nates in a state 

graph arid only the events in an evert graph are «^^ 

are now drawn as in Figure ZZ It should he noted that this practice in no way affects the foftnal 

'. ■ ■ ■ •- • •.. •■:■ •■ -' -: ,", • --< .■ J- <g ,.■ ■■ , ■.-.^..»«- ■-. , .. . . •.--«*'•' 

of state graphs and event graphs. 

(a) A State Graph 

'(b) * £n"lBvoht Graph 

Figure M Abbreviated 

rsji-f ^^^i*^i:*v.*t*jvs^TT-,v ; --^^^^^ig^^s^wr^*.^ 

Definition: If N-<S,EJ> It a Purl net, then R-«SM'.F'> to a Hssl ITOTOItlft "* N iff, 

(a) R tea connected, non-empty statt graph 


WP^FrtrxiuExsO 4 

k to a cosmottad, non-empty statffreph subnet of Nt In which aV am connected to a 
Deiticunit^sttttamiisee? V >*~\ V 

Definition: If N-eSAF* to a Patrl nit, than R-cA', 1', C> to an evem component of N iff. 

(a) R to a co nn a cf a d, nan-empty event graph 


(c) F' - Fnfcxl'u E'xS) 

•R to a connected, no n -empty event-graph subnet af N In which aR arcs oomadad to a 
patticipetsns! event ara used." 

:1, ;^3 *fif* * : "' "'i *?; 

Sf*0> " -'jj *■ : "» , ''"-j v -' c- if.- : .,57f 

Definition: A Petri net to said to be sttm*ranh <km— nbfc <*GD) iff each etemam (and thus 

e^™^^^™ip ^■* ^w^wsw ^mosifi^HBVsm ^us^swsn ^•^w^w ^w^wwa wwu/ aw ^^w^wew n» w^% 

In Figure 2.3, we show a stafegraph iirnnuuisHsn and an erent-graph decomposition for 

the Petri net N. Each of the two nets in Figure OW is a state oampofant of ft, and each of the 

two nets in Figure 2J{e) is an event comp one n t af N. Notice that each state component selects aH 
arcs connected toaitatcbutjustontsrcimesjidomarcoiitofeach event With an event 
component the situation is just reversed: it sates at any fafwenTidfoan eveht but just one arc 
into and one arc out of each state. In the case of N. there is a ittleut tttRt-grepti decomposition 
and a unique evenfrgrtph rt s mm e w i tiu ii. But, as well tat later, there may be several 
decompositions of each type doe to overlap of 



8* c 

B- «H'-' 


4J a 

M V •* <*' ll '»■.;■■. -^Iftte- «^- ? ■.«&..■ 

,Q "» m V " l0 "'**' £ ' ' *" 

■V :%*.-* 

;. '<*» 





10 -H 


U 4i 








to jo 




i ^'■^SjWsi/.S^-fr'SSSftri-si-i 

Definition: A circuit it a (directed) path whose two endpofaits art the same. An elementary circuit 
U a circuit m which no vetfex ts 

Lemma 2J: In a Petri net, the intersection of a tfttf 
• (oosatbtv emotv) cottMtia^-ef dkMnt 


event eesnaonent it a 

Proof: Let $ be a state in the intersection of a Hate component and an event c om p onent Because 
0ie state comoonent contaJail nil i«t lata^niHIo and franfYientie die event comooncnt 

»"i w^^ww* *nm'ia**M ■ wm Mfffnawt* fane . awaptav aunuMpsuiBB aw* aaajoes ••wjapw • .uwejoonap hio ofwi* %*#oaaaw^aoa^»aa» 

chooses exactly one ta6B& m^ ^0m^^^M^ n ^^ 13 ^ uim Just the two 
arcs of the event iiaisyjiim. By a o^l afljunteot \*»' 
incident arc and one emerfam arc for each mm. Twos, eac# clamant in the intersection 
has exactly one I ncident arc and one e m e rge n t arc The of** tmm structure satisfying 

Wl^eW i^^pwi^kwlWWa? H •» ^^^^Kto^M wv WJDVuW VtmsmolHowHuY Ue^BKsV U 

Theorem 2J: In a Petri net that is both SGD and EOD, every stale component and every event 
component 9 strongly coRnaccea. 

Proof: We prove the thecfem for state componfnta. the proof for events 

•ymmetrkaL Consider «n arc <x,T>in state e/ — " — "*■ " *~ J 

an event comp o n e nt K that aho contacts <*, 
.and R. By the m^ing kmn*, <xf>mm 

intersection of X( and % ThUmeiM t$at Q — 9r ^ m „ .^„ ,. 

elementary circuit Now from the def mMan '"of • state eamponem, "w« 
cormecfea. from these nut two facts* it 

ts being 
there is 

4* Q 

in tne 
by am 
chat Q is 

2A The Simulation Rule: 

In Section 12, we gave an informal description of the simulation rule for Petri nets. In this 
section, we formalize that rule. Our scheme is patterned after the Js^rence graphs' of Holt 001 
The basic idea U very simple. Oiven an mifettsed Ptari itet^ Streol>#oi» Rule generates all 
possible finite 'simulations'. Each simulation expresses a causal relationship among a set of stale 


•holdings' and event 'occurrences'. The causal rote ttemh l p reflests the pattern of WjinatfW Mid 
'inittatlonj' of hokllngi by occurrence*. 

A simulation is represented »» net «H.O, G> in which H is the set of holdings, O ii the set 

of occurrences, end C is the causality relation. In order to distinguish between repeated instances 

of the same dement, an instance (either a holding or an occurrence) is represented as an ordered 

pair <x.n> where x is an dement ,- the Instance type' -and ni* a positive integer - the 'instance 

number'. The Simulation Ruk is defined recursive^ ^.If^sfnnjata Is a collection of 

isolated holdings of the form <j4> where * is an initial condition. In a simulation, the set of 

unterminated holdings U referred to as the 'front boundary' of the simulation. When there exists 

a set of holdings in the front boundary of an existing simulation consisting of one holding for 

each precondition of Event #, then a new simtlatsan can be generated. The new simulation 

contains one new occurrence for Event t and onenew holding for each of /s postconditions. The 

new occurrence of * Wndnates' the previously uirterminatd holdings of #'s preconditions and 

'initiates' the new holdings of #'s postconditions. 

To create new instances, we employ an auxggary fm&m* 

Definition: eX*,Q) - {«, IQrXMxNJHfc} 

n(x,Q) creates a set consisting of a new instance of Eteatentx The msttnee number to one greater 
than the number of instances of x in a As a resuk, instance i » for an dement are assigned 
in numerical order beginning with L 

We're now ready for the formal simulation rule. 


Definition (The Slmirtotlon *«!* If Z * the MHMI— I Pen n*+> I» J, I» Own, 
(I) 4*[l)44> Is a tjQujgon.of Z. 

(2) If T ts the exlstfef BftmikKtw 4M), C>*nd if A to a i* of toMteft' In the 
front boundary* of T rowiMlm of out TieMing;' for each pfeosndftftsn of Event #, 
then, ' */< t.'s'i -f"r*> * , *n ■ 

F,tt.S; . »»*■ 


O UefcO). 

(s) Tm flwiy ftaaato|qf z*tt ttaom» o i iy« mw t» 

Step (2) is iHuttrated in Figure Z4. 



■ ■'■■ *. ■:'< :\ [■:'■■;■.- 1 


Definition: If T te the simulation <HAC>, then, 

O U tht tot of 
C is the 


V We're using a rotational convention here, ft W 
etsrnents In the rango of f on am, thou for JfjjQ, 

Thm.f> a ,H)-^.fXf,H)L 

; oP 

f ta a tnd If the 


The ordered pairs in C are the etenwntanr caw*l oayctiom of T. Occurrence q is 
said to terminate Qnjgajt) Holding h iff then is iMpfffprf % «-»> """^ 
leaning fromhtoqCqtohXThesetof utnstmi i wMrtfo nlnltsatod) holdings is celled 
the front (back) boundary of T. 

In the graphical representation of a sirouwikw. the vertices are drawn as points. The 
simulation in Figure 23 is one of these generated from the net in Figure 23(a) with States a4, and 
g designated as initial conditions. Because instance numbers are redundant in a graphical 
representation and because they might be confined with event name*, they're usually omitted. The 
abbreviated form of the Umukbon in Fsjure 23 is shewn to) .Figure 23. Note that this practice 
has no effect on the fjrmal representation of a Hmulatton. 

The following four propertiei follow Immediately f ran the simulation rule. 

Property 2& A simulation is a «et. 

Property 2A An occurrence of an event tewnfcales ont holding of each prec^^ 
and Initiates one hotmng of each p oitc on d m op. 

Property 2.4: A holding it initiated by no mow than oweecurrencB and U terniUiated by no rnore 
Mum one i 

Property 2* A simulation is circutt-f ret. 

Definition: Consider the result of taking the transitive and reflexive closures of a simulation. 
The new structure is transitive, reflsxive, and - because of Property 23 - 
antUrnmwtric In short, ttU a partial order. We wts»*&* indicate that x is related 
to y by this partial order, and x<y to indicate that x& but x*y. We adopt the 
following ter rninol e g y t 

x-y - xand * arc coincident 




<b,l>\ (d.l^ 


<a,2).' <e,l)X <g,l) 



<c,l>V <d,2>.^ <h,iy 



<a,3>* <f,l>X <8,2> 



<b,2>% (d,3).^ <i,l) 5 


(8, 1? 

<a,4>^ <e,2>X (g,3> 

(d,4).^ <h,2f 


Figure 2.5 A Simulation 


a • 

1 •: 

2 •; 

l • 

g • 

Figure 2.6 A Simulation (Abbreviated) 

:■;;=*&; rfa^^jw^^^ . 

f foBooe * 

*iy A y 1* - * and y art concurrent 

(Note that by our convention an Um*n<* y mad si itestf and foHows itself. This U not 
normal usage, but it's mora canvwrio^ %p our pmyam Net** that concurrency is 

nofhinc mora then tha ahomoi of anaoMha J 

t nv neat property iono^ SMeuiy ihm hh vanvmi imhv< 

Property 2ft If tha instances of Element x are totally ordered hMMmuattlon T, and if <x«m> and 
<imi> are instances m T, tha* «**> la the aaa^aaaMee of a fatowang <ayn> Iff 

We now establish tame baste structure/ lettfenaMps bet w ee n Petri nets and their 

then each 

Notation: If a Is tha instance <ayi>, then f • k ^hs notation is extended to a sequence of 
instances m the obvious manner. If ♦ is either an bufanra or a path in a simulation, 

•••unrw- w ■ ana aMniovn^B ouor ^^H ^^Ef ''a, 

Theorem 2.2: If T to a simulation of the tntttataed Petri net <N4>. then, 

#«ncr) # Hn.w s 

The image of a path in T is a path In N.' 

Proof: Every we in T it either of the form <hotd*y, utun ie m«> or <oceurr«nce, hokHhgx Thto 
together with Property *■> h»ds » «*» ioHlili lW l l D 

Definition: A strand of a simuletton is a path orifinattnj in the ■•** boundary of the simulation 
and terminating in the f root boundary. 

Definiton: If T«H,O.C> is a *imulatton of th« teittatad Peirt n* <SsW> and if R to a subnet 
of <SJSJ>, then 

forAfiHUO: A R - {qaA^e^RUE^} 

'A R contains those instances in A that hail fifcjfcei wMiln R.' 

forBsC: B R - {<^r>cBK^*fxFi} 

•Bj contains those ares in B that hav^iineferwuhin R.' 

Property 2.7: If T it a tfmutottoo of the WttaHied Petri net <N4> and R U a subnet of N, then 

Property 2A If T.^O,C> Is a stmiilatkm of the Wttaaaed Patrt net <SJE^4> and ft to » aubnet 
of <S£J>, then, 

F K -Fn(S K xC ft UE ft >e5 ft ) * C R - Cn(H 1 x0 1 U O^xHr) 

If F R constott of an arcs On F) connecttaf two 'elemental of R, then C R consists of an 
ana (in C) ce im ti ttng two le s tin i ui of T»' 

Property 2.9: If T - <H,O.C> U a sfcmrietion of the huaaJtoed Petri net <NJ> and R is either a 
state component or an event com p one n t of N, then, 

C R - CD(H R xO R U O r xH r ) 

*C R consists of all arcs in C connecting two instances of H R UO R .' 


Theorem** If T to a timukdon of tip t n^hwri F ^|^ <N^ wrt R to > «^ coropomniof 
N. then T, consists of g^ saJ Jrial ihl»lll ' 

Proof: If T U the initial limuktkm of <NJ>, then T K canto* of the hokitngi in I K x{|}. They 
fofm Igt disjoint strands. 

Now suppose that <H t , 0|, C t > is a simulation of <N, I> for which the theorem is satisfied, 
and that <H t O x , C,> to derived from «H I# 0|,G|> throufh a single application of Step 
(2) of the Simulation Role. Thus, there exists an event t and a set of holdings A sn the 
front boofw^ef ^.O!; Creech thet, " : 

H l -H|UnU',H 1 ) 
C, - C t U AMntnO|Ml t^WMJ 

From Property 2J we have, 

There are now two poutbilttiec t is contained in R. or t to^ contained Jn R. In the first 
case, JAjl - Ke^.0,%1 - Xe>'^i%l - L And in the second JApJ - Kfie.0,^1 - 
KeX«'^ 1 » m | - a Either way, tht theorem it satisfied for ^O^Cjx D 

In the net of Figure 2.7, there is a '2-token' stale component corittotmg *f those states, events, 
and arcs that lie on the outside ring. According to Theorem 24 (here should be two strands 
associated with that state component in each sh^ 

the simulation in Figure 2A Notice that the net in Figure 2.7 contains another 2-token state 
component - the inside ring - and four htoken soste components. The reader may verify that the 
simulation of Figure 24 contains the ■p p t op rltte num h n ejf i traji t > tor <ach of these 

* H R | is the number of 'tokens' on R. 

1*W ,^'« ,Xs ~ 



Corottary 24 If T to a stoufcttan of the mttteUud P*ri Net ^4>. ond R to a 
co m p o nent of N, then T K consists of • single strenoY 

Corollary ZZ If <H,O.C> to a simulatton of the inittalixed Petri Net <K,*r, and R is a Hokcn state 
component of N, then the instances In Hjj[ U 0* are tetOf ordered. 

Corollary W If T to a tonrtetton of an Initialized Petri net covered by Hoken state components, 
then within Tine tnptaness of each etonsnt w totals ordered. 


e • 

Figure 2.8 Strands of a State Component 



Si. Agumftjonj: 

Like any theory, the one 
rM following: 

here to bo*ei^ owm i n ii i jjioni t oni . Tim major one* are 

(1) Associated with each system to a Mt of Ham ( c onditi o ns) and events - the system elements. 

(2) The loftcat aspects of system behavior can he com p l e t e ly expressed in terms of the 

thai a system 
of behavior. 

(S) Petri net* am an appceprtottt tool for i mrs mi sf ie f the leg**! 
pieces on the holdings and occurrence* of its eSsmsnts. 

(4) A system may be decomposed into soajoenttai ""P**"** ^"* th * 

■ mdiieoB o^M>mimieBjBnBjB]i|(Bj|t%ae«^ "PRJiiR|^w*i 

[fi) fcvory system ossmoni4Srpnr( oi*o* oBW'ejm^j^^eesw^i^PwwyT^^^PrW*^** 

Assumptions (1) and (D represent en attempt to find » common ground for describinf the 
myriad facets of system behavior. The notions of s*tt, event, holding , end oeoirrence appear to 
be general enough to encompass everything that one ndght consider to be logical b e hav io r *, Note 
thar^ are^epeetftmty^ ' for 

be a f »»*• wi-<*4****rWM ihm 
of its element* Experience with 
«cb enpflmmts. ThUis the basts 

Because weVe deeiinf wRh finite systems, 
constraints that a system places on the holdings and 
Petri nets ha* shown them to be ideally suited for 
for Assumption (S). 

: 1i«*!*!§^ 


The most natural wr> of tntr o d d tif Hit iHBon of etarnattveneu Is by auumtng the 
existence of sequential co m po n e nts . Each sacfc aBmpontnt induces a natural partition of its 
elements into alternative dessos. (To bo captained bssew). By aawmlng that alternative dassos 
from different comp o n e nt! do not perttaBy overlap* we get a partttkm of the entire sot of system 
elements. This is the meaning of Assumption ffi 

Assumption (if UHHUosei the astern of s»oa1fo»ar Inmavlot. Hr-aj nan hat been an 
important concept in many different dlicsaltnoi, tut thest iiiUpimai have been b aiod on 
continuous models white ours is bawd on a djsgotj. taodoi The fact mat steady-state appears in 
conjunction with a discrete modal should not be too surpt i i tog m o ugti . After ah, we're trying to 
describe the same reality wheal* wVWvitfhM 

The f fre sjsgf np t hw w Hi JHittWIITw li^ tunem. This definition 

incorporates five axioms. Akfcougti men axioms eachate many mmrtun and maaningf ul nets. It 
has so far bee* poomw m convert seth nor Tnif mffMmmmm^im mmfi Much more 

^••■^•e MIVb So) sTo^b^R^o^mV w9 1 


SX. A System? 

in tie proDBBing cneeesr 

wmsejngumiee wejamewtPiiaMpsHR^ . 

We do the same for 
structural properaal or a 
mtaauzea system. 


system This soshon and the next throt are 

of an 

.',->'. ; . '--.« t6s3a"'^ rf-> 


of «iw and a set of tubtets of events. The subsets of stet* an used » |«mm a covering of 
state compononti - the 'parts' of the system. The wbiw of tvontt aw uwd to gonwalt a covtrtng 
of evemeix«ponei»-theVoedes'ef thesysteni. WeceoMtof ^eiii^liav#liKlujledlNpamafid 
model themselves in the def tuition of a qmm, ****•?*** haw beta a grmt deal of 
redundant information. We're taking advantage of the fact that a state component U uniquely 
Identified by its states, white an event component U unkaieH; identified by to events. Note** for 
a given Petri net, there may be several covertngi of both state components and event components. 
The constructs of the theory will, in general, depend, ju^ w«ch^;coferlB|i am setecttd, but the 
implications of this art not fully understood. 

Def initlon: & - <N, Dp, Djn> where, 

N - <S, E, F> is a Petri net - the svttem ne£ 
D«£(P(S)UthepartdjffiGffiO»i^ r 
Dm^ s ^ (£) te the moi£ djccmpo^sp. 

X denotes SUE, the i^ttem etetwitt 

Axiom 1: Nil connected. 

This axiom merely prevents a system ftom having seveml dlouiiissirinrl oemaooonts. TWtisoota 
real limitation since in sucheaseseach connected cgmponert o^betieatedas a separate lyetem. 

Axioms S-UDp 
VAeDn: <A, *AUA\ Fn(AxEUExA)> U a connected, non-empty stale graph 
The sets of stales in Dp genemiea eevertng of stata components.' 

1 OKA) denotes the power set of A - U, the set of all subsets of A. 


Definition: The state components goaars as d by the MO to Pp are catted <he parts of £ The sen* 
parts it denoted by p. 

When the spum J ii tatttattM* ve wit rw p Urs th at o* h psot bes j i iy so d oa s aly one krtttal 
condition. Thu% the ports wit besom Hohen itsie nnmoenewh end wit be tincwjfd with- strictly 

seojttentiel isehewtor . 
Axiom J: £*UB*i 

VtdOfjf «1U*', B, FA|**1WM<*)» is s essesa^ ttoo-esepty event fraob. 

The sett of events in dm tenenti a i 

Definition: The event component* generated by the sett in Dffl am caBoa the roodes of A The set 
of modes is denoted by % 

Each mode is to be associated with a steady-stats pattern of behavior. The reasons for this 
interpretation are simpls. If an event is involved in a steady itatt pattern of behavior, then all of 
the states connected to that event are also involved. For a state that is part of a steady-state 
pattern the situation is different Here, Jose one input event and one output event of the state are 
involved. So we me that is sod y suue u s IiaU st is m o wHI s ws sUa is l -wHh event c o n y o n o nis. In 
Section 1* welt strengths the eomwotion between *ts»dy«stojt* behavior art tfaoee event 
co mp on e nts that comprise the modes. 

Property SJ: Every part and every mode is strongly connected. 

This follows from the fact that N is be* 8QD and SOD, (lee Theeraro 2J) , 

Property 12: N it strongly con ne cted. 

Since N is conneeted (Axtom 1) end covered by strongly connected c ompon e nts (Property SJX it 
mutt be strongly connect ed. 

11 The Parts: 

The main reason for Including putt in our definition of t system is so that we can define 
the notion of akernativsness. We begin by assuming that sencurrency and akernativeneu are 
mutually exclusive. That is, if two system elements may either hold or occur concurrently, then 
they cannot be considered alternative. The most natural way of guaranteeing that two elements 

_ ■■:■-.! ^rv ... ' ..,;;,.,■>■. ■■---**:: ^ '*.?;<(*» T 

>.<■-. • - ■ -.. ■ fft 

win never hoM or occur conc urr e nt ly is to require that they both be contained in a single Hoken 
state component - that is, a part But we don't want to say that u se e le me n ts are aterrwtive just 
because they belong to the same part For example, if die part consists of a single elementary 
circuit, then no two elements on the circuit can be said to be alternative. There U a situation, 
however, in which two elements would definitely be celled alternative: when they are alternatives in 
a choke. Since our theory is intended to be ty n u not rfca t with respect to the forwards and 
backwards directions of time, we include bath f erwasds sM eeAwatds choices, In Figure 90, 
Events «i and # s are alternative, as are Events # 3 and « 4 . We carry this idea one step further by 
defining the alternative dostife' & ft put If two elemsnts in a past aft^ajteatiet**, then their 
immediate successors wKMn the part are aho akernatrtev as arerthejr irttnedhtfe predecessors. 
Thus in Figure 12. States ^ and s» at we»a» Stteas ^mis ¥ wm nfa w ii a il u - 


FfcjweM Aaeraedve Event* 


Figure S.2 AJtornett v« Statej 




Definition: The fbnffH^ rtTftn f ff fff f * «- --*~i -i-m- „ f r fv^ ..-u >u.» 
VxcXp: XpCjX 

W« uy that X} and x, are aj&»&£ 0* W iff *i*»*i but *|i«fc (We do not ay 
that on «h*n e nt to elteiontlv e wirt i met.) - ate* «* ,*«& « •— -*' v 

Thoaram It For Pe?, * P fc an cqutvannce reletien on the rttii ten tib f P, and, 
VA « Xytey; Afil V AgE* tJ 

'Each eQUivatamciau Mucosa? «, 

' If ■ is an equivalence relation on the «t X, then X/« 
induced by «. 

d e note! the set of equivalence chutes 


Proof: Reftexivity and symmetry follow diroctly from the definition of .-ece* f or transitivity «d 
the second put of die theorem, we make use of the fact that two elements are related by «tp 
iff there U a state f rom (to) which there exist paths of equal length boding to (from) those 
two dements* Thus if aipb and bdji m'Uk^fatm^ timtikm lit which h*,hhft 2 | 

• a 



Because a part is strongly connected (f r^serty SJX there exist paths jig and m as shown. 
This gives us paths of equal length leading from * to e and c - namely, stfstjstyii and 
MS*!**** Thus, e«tp£ and *p is transitive To set that a state and an event can never be 
a w stnaU ve, It is ertfy twceewjMo nott that eeiwasn iay two Half* aft path* are of even 
length while bet w ee n a state and an event aft paths are of odd length. D 

Now since «ep is an equivalence mletien on tht stoments of Pan ? , «tp;is>doeei;*' 

of P. 

Definition: For Pep, 


* This fact may be verified by the reader. 


Property 3 A P* is a ml 

The method of generating a quotient net ii iBuitrated in Figure 11 

(a) Part P 

I {b,c} 

<b) Equivalence Classes 

Induced by a 


Figure M 

(c) P 

Notice that the eoettant net In figure Si (e) tsaw etpmemafy efeeufc Thss is always the < 
What's more, the length of such a circuit is equal to the god (gnats* common divisor) of the 
lengras ot tne elementary qroms ubii esweiBeneme^aara 
Definition: If G is a strongly-connected directed graph, then, 

<jKO) - ged {n)n is me length of an elementary often* nN) 

Theorem $2r. For Pep, P* is an elementary circuit of tength ?<PX 

Proof: The definition of u f eliminated all branching, both forwards and backwards, in P*. 
Because P is strongly connected, so too is P*. it foMews that P* is an elementary circuit 

Let n be the length of the elementary circuit comprising P* We note that two elements 
belong to the same equivalence chut iff the length of every path be tw ee n the two is a 
multiple of n. Now each el e menta ry drat* m P may he viewed at a path starting and 


terminating at tht tame element Therefore, th« length of each ehvnentary circuit tn P mutt 
be a nwktpte of ». Thus, n £ 7<P). 

Let m be a path in P that makes exactly em Org* of 

length/is h. Let a and t be to two endpomts. 
ctastfthere must ex»W Han f from which I 
and IT 

P*. It begins and ends in the same 
Such a path dearer exists. Its 
ft are in the.mme equivalence 
<T e^ hngth-hwding to e 

Because P is strongly connected, there exists a path m 5 from t to s. We now have two 
circuits: py^ >nd »a*l** Since every circuit, elementary or otherwise, can be decomposed 
into etsmentary circuits, it fofews that t(P) divides me l e ngm i e^ j | cif<oi>» m P. In 

.pnrttcttlar,^^^ m*™T* 

also divide the difference between fc^) and%|^ But Bus Is just n. Therefore, 
yPp^n. ftbeae wehst sJrendt>ebeom mil fmyPn i inMwltt*^ffi* t Jp ^ 

The state graph In Figure 3.4(e) has two elementary drains, one of length » and the other of 
length 12. The quotient net induced by mis state graph U shown hi Figure 9.4(b). It is an 
elementary circuit of length 4, which is die g ed of 8 and Gt 



■4 »^| 




(b) P 


What we've done so far is to gtnerttt » iiparttt f*dtht Mt f or «»ch ptrt In order to 
construct a single quotient n«t for the wftra iyi«i> t ^^ ttt« 1»^« <e ipok »t the possible 
relationships between two alternative classes from two different parts. There are three possibilities; 
(I) the alternative classes are disjoint, <*) they partially overlap, or (S) they are Wentkal Since we 
need a partition of the system dements to construct a quotient system, we must exclude the second 
possibility, alternative classes that partially overlap. This is accomplished with die following 


Axiom* VP^PjC^: VfcXp^^: VrcXpj/^ 
ffTr-4 V f-r 
Two alternative ctattiei tre either «tjMHHV 

Figure 16 ithiitratei the type of notation that ta pfehtMted by this axiom. Part P t generates 
an alternative 4a* containinf ili«-«««Hla-«|'-«n»^%' ^WMt-^lptelii* an aRernaaw cku 
containing the single event «|. The two alternative daises overlap 


Figures. 5 Partially Overtopping Aternetive Classes 
At a remit of Axiom 4. we now have an equivalmet relation on tlw sit of syaem elements. 

Definition: u - J^eCp 

* »» the ajeragyjnjss. gajga& f * * 


Property 3.4 oi U an equivalence rttatlon on x,»»d, y „ rV 

VA c X/rf: AcS V Ac E 

•Each equivalence cJatMftdufid a? * m****** m**x*f state or exclusively 

Since « is an equivalence relation onto elements of the net N,u induces a quotient net of 

Definition: The control structure for $ U the quote* net N* - ** E* FS where; 

S'-tfi^lJtS} it^act $ 
E*-{I*^|«eE} (to meting! of £ 

X* denotes S«UE* We writer to nwea <**>€**. (Rota! that xy means <x.y> c F.) 
For^tX* ""\ . ,•""" 

PropertyS.5 N* to a ml (N* wi» m fctoprelad u a M net) 

The steps involved in generating a control structure are ffiustrated kfcF%ure SJft. Notke that 
the control structure mar be viewed u an tntsrconMttfcm of to ststontary circuits generated by 
the parts. From this we have to follo win g . 

- V*-*?»tv *-Wfc*,-$,"%. -**-"*-. ■i^^^S^M^i^^K:"..'-*^'' 


rg u <* <^ . *. « <o 



X> (•»(*>« KV tf> C »*» 














































Property 16 N* it strongly connected. 
And there is something else that we can say about N* 
Theorem SA N* to an event graph. 

Proof: Each link I belongs to at wast one part Lit P bt such a part Then / to contained in the 
elementary drcutt generated by P. Within that eJrwK. / has a unique input meeting and a 
unique output meeting. Because P to a statt component, theae two meetings contain all the 
events that are adjMent to the states in L fherafore, mere can be no other meetings 
connected to /• 

Since it to our custom not to txpUdtty show the states in an event graph, the links in a 
control structure will be drawn as . . . links'. Thus, the control structure tot Figure 16(d) win" be 
depicted as fen Figure 17. 




Figure 3. 7 A Control Structure (Abbreviated Representation) 

-*H-^'-** **-"" » J - *^"' *•*' 


Between the system net N and the control structure. N* there eiistt an important structural 
relationship, one that will be used in relating system behavior to control behavior. The 
relationship is Mntstrated in Figure 18 and is expressed by the fouowtag theorem. 

Figure 5.8 

Theorem 14 VecE: WeS*: 

/♦M* ~ I in*«| - 1 

The preconditions of Event # select ont state from each input hnk of W^-' 

Cr^*/ ~ |lfV|-l 

The postconditions of Event « stent one state from each output hnk of M^-' 





Proof: The theorem follows from then observations, 

(I) A meetine*m*nd««nkx4 an conn erts d « Ht Jfr these it * par* P each that m and / are 
connected in P*. 

(2) m and / atteonMcted in P* iff each -even *«* Mnasil s d tooaactfrooe state jtfct, 
(I) if et and I arenot conmct s d in W*. dw» woenn m I » es n g o t te d teen etc* m -et a 

15. The Mode*: 

The model arc event components of the seaserA »*;X. The event co m p on e nts of N have an 

Lemma XL If at is an event com p o ne n t of N, men, 

Vf/cX* PCiinfli^unrl \i, 

'An event component intersects all aksmativecevasei the same number of times.' 

Proof: An event component selects all arcs into and^iejaf an eveiit aiid one arc Into and one arc 
out of a state. Prom ija j i n jw It we then haveO 

■""-""jfT "-■■■ V' . i sp , "' : .-t -' "y* v 

- ■-<**■ ■ ■ ' . ' - " P "$T *. 

This fact, together with the cownocttvtty of N* pr o duce s the desired result Q 

Modes are the structures that correspond to iteadT-etatt paiterm of behavior. We shall take 
the term 'steady-state' to mean that a mode intersects an ehernauvt dass in no more than one 



Axiom* VMcflk VfcX*: PC M Hf| ^ t 

'Anted* and an alternative diss internet in 

In figure S£ we presented a system net together with a 
the modei In Figure 34 we yet e eamplstt systole, 

Wten these are combined with 
tetsfy diet Axiom 5 is 



Figures. 9 Modet 

From Lemma SJ and Axiom 5 it follows that a mode either dees not intersect any alternative 
class at all, or intersects each alternative dan exactly erne. But die first cut cannot be, since it 
would imply a mode with no elements. 


Theorem 15: VMaffl: VfeXV PCsjnel-1 

A mOOt IHWHlgl HOI awonienTe cs« oxacay once. 

Corollary 3J: VtaX* ty £ UN 

The tin of an alternative dan cannot be greater than the number of modes.' 

Theorem 15 together with the next theorem establish an tmpeftint relationship between each 
mode and the control structure. 

Theorem 18: VMcfll: Vx,y€X M : 

<*,v>eF M ~ M**W* 
There is an arc in M connecting x to y iff there is an arc m N* connectinf fej* to 

Proof : «► Definition of N* as a quotient net 

♦ Assume M^W*- Either x or><botno*botb>» an event Assume .tfi x. By Theorem 
14 and the definition of a mode as an event component, there exists an element x in 
X M fK^ such that <x > z>cFjj ( . But by Theorem St we knew mat mare U only one element 
in X M n lyl^. Therefore, y - z and <x,y>cF M . O 

Corollary Ifc VMalfc M is isomorphic to N* 

'Each mode is isomorphic to mi control structure,' 

We now have a nice visual interpretation fOf the dan ot nets produced by Axioms 1 
through 5. Each net in this dan can be viewed as an Interconnection of isomorphic event graphs. 
If we imagine the elements m each alternative class to be vertically in tine, then each mode wilt be 


roughly horizontal (see Figure S.10). In the top view, alternatives are indistinguishable. So too are 
the modes. Their projection forms the control structure In the side view, we can distinguish 
between the alternatives in an alternative class, and we can identify the individual modes. 


Control Structure 


Individual Modes 

Figure 3. 10 Views of a System Net 

From the structure of the modes, we can say something about the structure of the parts. 

Theorem 8.7: Vp€/>: VMeTTl; POM is an elementary circuit of length <y<P). 


Proof: P* is an elementary circuit of length <y(P). Since M is isomorphic to N $ , M contains an 
elementary circuit of length <y(P) whose image is P*. This circuit is also contained in P. D 

Corollary S3: VP«p: P is covered by elementary circuits of length <y(P). 

3.6. An Initialized System: 

Over the last four sections, we've established the structural properties of the system A We're 
now ready to consider the behavioral properties of the initialized system £.. 

Definition: £• <ZJ>pJ>n^> where 

Z - <S, E, F, I> 


VAcDp: |Ani|-l 

lis the set of initial conditions of I. 
Z is the initialized system net 

The third requirement says that I assigns exactly one initial condition to each part 

If we think of I as the system 'hardware', then the set of initial conditions may be viewed as 

the system 'software'. With this interpretation, a piece of software (Le. a program) has no meaning 

outside the context of a system. This is exactly as it should be. 

Since Z is an initialized Petri net, the Simulation Rule an be applied. 

Definition: The simulations of Z are called system simulations. 

Because Z is covered by 1-token state components, namely the parts, the results of Section 23 are 


Property 3.7: Within a system simulation, all instances of the same element are totally ordered. 

Property 3.8: If <xjm> and <x,n> are instances within a system simulation, then <xjn> is the next 
instance of x following <x,m> iff n-m-rt. 

We've introduced the initialized system net, and now we introduce the 'initialized control 
structure'. We use the initial conditions of the system net to generate a corresponding initialization 
of the control structure. 

Definition: Z* - <N* I*> where 

I*-{MeJ S€l l 

Z* is the initialized control structure 

In Figure 3.11(a), we show an initialization of the system net from Figure 3.6(a). In Figure 3.11(b), 
we show the corresponding initialization of the control strucure from Figure 3.6(d). 


, JtuVr^ ■%*•"«- s 

(a) Z An imuaased System Wit and 

Definition: Th« ilmuhtlom of Z* are celled control simulations. 

In an event graph, each elementary draft to aauifcteen^aeht, and vice vena. The control 
structure has a special covering of elementary circuit! gw e wl e d by the parts. Because each part to 
assigned one token by X the corresponding elementary circuit to assigned one token by I*. 

Theorems J: 2» to covered fcyBefcen state c onyene m 

Coronary 5.4: Within a control simutauon, *H 

instancei of the same alternative data are totally 


Corollary 3.5: If <qjn> and <qji> are instances within a control simulation, then <q?i> is the next 
instance of q following <qjn> iff n»n-*i. 

We now show that for each system simulation, there is a corresponding control simulation, 
and two simulations are isomorphic 

Definition: If T is the system simulation <H,O.C> and q e HUO, then 
©T<?> " < W3*« KrcHUO | r£f A htf}\ > 

Gj(q) is going to be the image of q in the control simulation corresponding to T. Notice 
that Qj(q) is an instance of the alternative class to which 9 belongs. Thus, if two instances in T 
are associated with alternatives, then those two instances will map into the same type of instance in 
the control simulation. Because of this, the instance number assigned to &f(q) is not necessarily 
the instance number of q. We must count the number of instances in T that precede (£) q and are 
associated with the same alternative class as q. The instance number of 9j(q ) will never be leu 
than the instance number of q. 

Definition: If T is the system simulation <H.O,C>, then, 
T* - <e T (H) l e T (0),» r <C)>t 

In Figure 3.12(a) is a simulation of the initialized system net in Figure 3.11(a). In Figure 
3.12(b) is the corresponding simulation generated by 6^. Notice that the second holding of State b 
in T corresponds to the third holding of Link {b,c} in T*. 

The next two theorems establish the relationship between T and T* and the relationship 
between Z* and T*. 

T 0t(C) - {<%(?),9 T (r)>|< ? />eC} 


a • 

2 •: 

d • 


e • 


c ■ 

4 > 

a • 

7 • 

1 •; 


i • 



e • 

(a) T 

Figure 3.12 Corresponding Simulations 






"■ c }\ W 
{a}/{./K {g} 

c} \ {t} / { *- ,} " 

{0} / {e,^. {g} 

{d} /{M}' 


(b) T* 
Figure 3.12 (Continued) 



Theorem 3.9: If T is a system simulation, then 9j is an isomorphism from T to T*. 
Proof: 6x *« clearly onto. Now suppose that 0r(ft) - 0T<ftX Then 


Kr | r*ft A r^JI - «r | r£ft A fVfyl (2) 

Let e - [f ^ - [9 2 ]*- Since e is an alternative class, there exists a part containing all the 
elements of c. Consequently, the instances of elements belonging to e are totally ordered. 
Line (2) says that ft and ft appear at the same point in that total ordering. Hence, ft - ft 

and T is 1-1. If C is the causality relation for T and C* the causality relation for T*. then 

it follows immediately from the definition of T* that, 

<q,r>*C 4» <6r(j), 9i<r)> « C* □ 

Theorem SJO: If T is a system simulation, then T* is a control simulation. 

Proof: If T is the initial simulation of Z, then T - <Ix{|}, +, +> and T* - <{Ci]eJs«I}x{l}. ♦. ♦>• 
But [bXtUel] - 1*. and therefore, T* is the initial simulation of Z*. 

Suppose now that Tj satisfies the requirements of the theorem, and that Tj Is derived from 
Tj through a single application of Step 2 of the Simulation Rule. Let, 

Tj - <Hj, Oj, C!> T 2 - <H 2 . Oj, C 2 > 

V - <Hf, Of, Cf> T 2 * - <Hj*. Oj*. C,S 

Now there must exist a set of holdings A in the front boundary of Tj consisting of one 
holding for each precondition of an event « and such that, 

H 2 - H, U *e\ rty 
2 - Oj U fl<«, 0{i 

C 2 - C t U Ax^.0!) U iK#,0 1 )xiK* , ^ 1 ) 

We must show that a similar relationship exists between T t * and T 2 *. We note that 
M^ c E*. Let A* - 6t.(A). Because A is contained in the front boundary of Tj. and Q Tl 
is an isomorphism, A* must be contained in the front boundary of Tf. By Theorem l«a 


& b), A* consists of one holding for each precondition of U^. For the three component* of 
T 2 * we have, 

H 2 *-e T2 (H 2 ) -e Tl <Hi>ue Tl <f(«\H 1 )) <»> 

o 2 *-e T2 (o 2 ) - er^juer^Oi)) (2) 

C 2 * - {<8r 2 (f >.e T2 (r)>l<f,r>eC 2 } - {<e T2 (?),e T2 (r)>|<?,r>eC 1 } (3) 

U {<e T ,(f).e T .(r)>|<f,r>€Ax^«,0 1 )} 

z z 

U {<Q Tl (q)J^ l (r)>\<qjr>€^*,Oi)^'Mi)} 
Since Ti is, in effect, a 'prefix' of T 2 , we have e^C?) - e^fo) f« all f tfliUOi- Thus, 
9 T2 (A)-e Tl (A)-A* 

©T 2 < H 1> - OtjWi) - H l* (4> 

eT 2 <Oj) - Bt^OP - Of <5) 

{<e T2 (?)« e T2 (r)>|<?,r>eC 1 } - {<9 Tl <?), 9 Tl (r)>|<j/>eC 1 } - C t * <6) 

Let <s,n> be a holding in ^'.Hj). Because [s] u is an alternative class, there exists a part 
containing all the states of b] u . Therefore, the holdings of states belonging to b\ u are 
totally ordered in both T l and T 2 . Furthermore, <*, n> is the last holding in the total 
ordering of T 2 . From all this, we get, 

BtMi'Hi)) - {<M*.«>I *«' »"d « »* *« number of holdings in H 2 of states belonging to 

- {<[i] oC ,n>|i€<* and n is the number of holdings in H t of states belonging to 
Wot " P ,UI U 

But by Theorem 14(c & d), {tsjji«0 - {WJ &k« W^*}. This, together with the fact 
that 6-r is a bijection, gives us, 

Gt,(iK«*. Hj)) - {<&]*» n> l M* 6 M** and n u the number rf *n«ances of D]^ in 


Hf- plus 1} 
-iKM^.Hf O) 


e Tl <i(«,o 1 )).t(i#k.<V) W 

From Lines (7) and (8) and the fact that 8t s <A) - A*, 

i<9rj*>. *r,M>l<f n * a*^)} - A'xefl^.0^ W 

{<%,<*>. «T 2 <'W<f/> iffcOj^e^fftf - '#^f» ^«f©U*. »1*> (l0) 

Finally, wt get, 

H^-iyuoH/.Hj*) Llnesl,4.fc7 

O^.Ot'UfCU^.O!*) Llnes2.5.*8 

C,* - Cj* U A*^^*) M.^N^^') *•*"•* * 6 «* * W 

Since, by hypothesis, Tf i» a sMatton Of Z», m must condudt that T,* to also a 

simulation of Z*. ° 

Coronary SA For aach spam ismutotfon, there to a cormawKUr^ control tkwriathm, wrf tiw Ww 
simulations art Isamorphlc, 

Nam that the co r r aipoii d anw bttwawi iyn«rn Urmdatlom arid oootrot stomilaaero to not, in 
general, one-to-one. In mo* cam more will be si sy*sm sUmitaitoru mapping into a single 
control simulation. 

8.7. Examples of ffffllMlltf ffTftffTT 

In thUstctton.i* present thr«ttx»mpte» of mitialtooi systems. For each one we provide an 
Interpretation. The formal technique! developed in the J|«ewii|h<cha|>tefs will confirm these 

The inittahwd system depicted in Figure Sfl r e pres e n ts a three-*age bit pipeline The three 
parts comprise the three stages. Each made mm^^ Ujlm^ttim^ <*"*"* , b^format^on^ 
•Bits' enter at the topmost stage and are passed from stage to stage untU they are lost at the 
bottommost stage. 



' 1,,: ' -Iff'- t , ' V '"- S ' i *- ; 1 V 




«■ * 

f» en 

y*-i ■" ';%-V 














(d) Initialized Control Structure 
Figure 3.13 (Continued) 


Tht inittatiMd system shown in Figure 1W to formed by taking a four-stage bit pipeline and 
connecting the first and test stages. Tht remk toa ctroiktttnf Wt pipeline. Netke that in this case, 
•tots' are conserved. 

The initialled system of Figure JU5 desoiMra half adder. The choices associated with 
States a and » represent the two binary (npetr. the reverse chokes aseadated with States k and / 
represent, respectively, the sum and carry outputs. Thert are four modes and they correspond to 
the four possibtt operations. Notice that the system net is covered by four Hoken state 
components. We've chosen two of those i| ear parts. Although the choice Is arbitrary, it has no 
effect on the resulting control structure {There pm. however. sttuetions in which this is not the 
case. The net in Figure 116 U tn examett. Defending on which covering of state components is 
selected, either of two control structures wM be generate*. The ssinsfkancc of this is not yet 


(a) Initialised System Net 

Figure 3.14 circulating Sit pipeline 


1 1 

6 6 

5 5 

(b) Parts 

Figure 3.14 (Continued) 





(d) Initialized Control Structure 

Figure 3.14 (Continued) 

-t r - * , - ft . ■ 


Input A 



(a) Initialised System Net 

Figure 3.15 Half Adder 



\ I 



*-* in 








*-. m 






i n M i . ii M i nn U ' JEa i 1 





o -4 





{,,2> R 

□ M 


\\ w 

1 xt ef } 


Or 1 

\H i} 

{*-}\ /v 


{^w)0 * 



(d) Initialized Control Structure 
Figure^ 3.15 ^C^i#6ittued> 

Figure 3.16 System Net with Two Control Structures 

*--. -, ■■.^. < a^'^*^*^'a*fe**;^ 



4J. Inf orfnation, CggasE 

In this chapter we continue with our study of the system A In Chapter S, w« showed that 
the control structure N* d e t e r m ines those sJpffti of behavior that result when alternatives are 
made indistinguishable We are now Interemd in provUinf the ability to distinguish between 
alternatives. We introduce the notion of 'Information context' for that purpose. 

Definition: The set of parts contaiiUng Elemtnt vis denoted by ?(xX The set of modes containing 
Element x is denoted by UKvX 

Definition: ForxcX, 

Kx) to the set of modes excluded from ^ Ifat) to rtie inf ormation content of x. 

The reason for defining information content as the set-el excluded rather than included 
modes has to do with the (psotuttoa of xhokei. This if dbxnsswl m Sections 43 and 4.4. We 
might note that when an element has no akemauvei, there ale no modes excluded (Theorem W) 
and. therefore, the information content of the element is mnt 

It to convenient to associate a color with each flwde. The information content of an element 

' This resembles a definition by Heft and Commoner 0S1 bi the context of a strongly connected 
state graph, they defined the Wormxtion sst'ofastatetebethesetof excluded elementary 


can then be viewed u the set of colore associated with the exduded modet. In Figures 4J through 
43 ere the system nets for the systems described m Figure US through SJ5. We've associated a 
color with the events defining each mode. Next to each system element to its information content 
expressed as a set of colors. 

We now show that inf ormattori content dots iedeeddtottnguish between alternatives. 

Theorem 4 J: tej^cX: 

If two elements belong to the^s ^ateama ttve dm and have the same information 
content, then they mutt bJMue simeiehMpBW v * 

Proof: * Obvious 

* This part of the theorem foltowi ftnm thew ebesnfationi. 

(aJI^W^^Wxj^TWxj) s 

(b) Each element is contained » at toast one j 

(c) An*odemteriectotniltenMUireclattmexacth;cmfhwm»»t □ 

So now a system element can be uoje^ JdeMtfJfd -bjr spedfytog two things: 0) the ajternattve 

45. Inf ormation Flow: 

Suppose that qj and o^ are instances in a system il mutetmn , and that there is an elementary 
causal co nn ect i o n leading from 04 to <fr 


Red = {1,3,5,7} 
Violet = {2,4,6,8} 

Figure 4.1 Bit Pipeline - Information Contents 
of the System Elements 


Red = {1,3,0,7} 
Violet = {2,4,6,8} 

Pigure 4.2 Circulating Bit Pipeline t Information 
contents of the System Elements 


Green = 

j 1,3,5,9,10,12 


j 1,4, 6, 9, 11, 12 

Orange = 


Violet = 


Figure 4.3 Half Adder - Information Contents 
of the Syetem Elements 


Let qj be an instance of x v and q 2 an instance of x 2 . Associated with q x is the information 
content of Xj, and associated with q 2 is the information content of x 2 . We shall interpret the 
information that is common to both Xj and x 2 as 'flowing' from q } to q 2 - 

Our convention of associating modes with colors permits a graphic representation of 
information flow. The arcs of a system simulation are colored according to the following 
algorithm: An arc connecting instance <X|,?t|> with instance <x 2 ,n 2 > is assigned a particular color 
iff the mode represented by that color is contained in Ify) n I(x 2 ). In Figures 4.4 through 4.6 are 
some simulations for the systems described in Figures 3.13 through 3.15. Using the correspondence 
between colors and modes given in Figures 4.1 through 45, we've indicated the colors assigned to 
each arc The reader is encouraged to do the actual coloring. Note that some ares may be assigned 
several colors, while other arcs may be assigned no colors at all. 

This formaliiation of information flow corresponds remarkably well with intuition. In 
Figure 4.4, we can see quite clearly the flow of "bits'* down the bit pipeline. The two colors 
correspond to the two different bits. At Events 1 and 2, bits enter the pipeline At Events 3 and 4, 
the bits are transferred from the first to the second stage. At Events 5 and 6, the bits are 
transferred from the second to the third stage And finally, at Events 7 and 8, the bits are lost 

As expected, in the circulating bit pipeline, bits are conserved. As shown in Figure 4.5, the 
same two bits are present at the beginning of the simulation and the end of the simulation. 

* The notion of a *bit' is very restrictive and is used hen only in an informal manner. Formally, 
information is expressed in terms of excluded modes, not in terms of bits. 


1 •; 

b y 

d > 

a .• 

e •. 



c % 


4 > 


7 > 

* ■•- g 


1 • 

6 >: 

b > 

d .• 

3 ;•: 


a • 

e V 



g • 

Figure 4.4 Bit Pipeline - Information Flow 


• J 

• c 

Figure 4.5 Circulating Bit Pipeline - Information Flow 

















With the half adder, the situation become! more complicated. It it no longer possible to 
interpret information flow in terms of bits. But the flow of information still corresponds to our 
intuition. As shown in Figure 4.6, information enters at the designated inputs - Events 1, 2, 3, and 
4 - and is lost at the designated outputs - Events 10, II, 12, and IS. Notice that in each of the two 
middle simulations, information is also lost at an interior event In the '04' operation, the color 
orange is lost at Event 6, while in the 'l-ttf operation the color red is lost at Event 7. At Events 5 
and 8, there is no such information loss. The reasons for this are simple. In the case of both 0-rt 
and 1*0, we get the same outputs - a sum of 1 and a carry of 0. In these two situations we are 
unable to reconstruct the inputs from the outputs. The information lost at Events 6 and 7 is what 
allows us to distinguish between OH and 1*0. In the cases of 0*0 and 14, the conservation of 
information at Events 5 and 8 corresponds to the fact that, in both cases, the inputs can be 
reconstructed from the outputs. This short discussion is a preview of the ideas contained in the 
next two sections and in Chapter 6. 

We mention now an interpretation for information flow that the reader might find helpful. 
We've shown that the control structure determines those aspects of behavior that result when the 
alternatives in an alternative class are lumped together. We've also shown that information content 
provides a way of distinguishing between alternatives. Our practice of associating modes with 
colors then permits us to think of information as colors assigned to the 'tokens' on the control 
structure. The colors assigned to each token determine a unique system element By defining 
appropriate color transformations for the meetings in the control structure, we can duplicate the 
behavior of the original system. 

4J. RqylyjftgClwks 

. ^. We've tttt nethief te far 

resotutiort of cholcei teofc* 


coafemt and 'the 


We might ask how the tatfartratfait c o ntent! of « ant * art rohtfod, The foflowtng 
answers that qiMttton. 

w * I<#)-Kj)U !«*•-{#)> 


♦* * IW-Kj)UWVW) 


Thr infnniilim «ntpt #c ipeji rtn bifaimiw 11 
model cowtof •§ eatprt Qapat) own* ef * eaeipt *• 

«t tlwi ph* the Mt of 





Proof : We prove just Part (a). 

Because an evert ampenamsele&eUa^ 


Since *cj*, 

Ms 9 ) - W*> U TftU'-W) 

B«aiuie TTK«)nTIKi '-{*})•♦ CTMowmW), 

TW«) - Ms) - W-W 

From thedefmitioneftofonnetioa content we get* 
Corollary 4.1: VxcS: V«e£: 

(«vw) # IWcK*) 

The Information content of an event contain* the information content of each 
precondition an« each postcondition of the event' - 

To iltuttrate Theorem 4.2. we note that in Figure 4J, I(S)-{Y}, I(d)-4, and M4)-{V}. So we 
have I(3M(d)UlTK4) u predicted. Coronary 4J meant that, with our scheme for coloring the arcs 
of a system simulation, the colors entering and leaving a holding are the same In other words, 
colors appear and disappear only at occurrences. 

Whit is the significance of Theorem 48? to the case of tn, t is one of the aim nati » n in 
the forward! chalet associated with i. Whin Hm olHWoHs iiiujwissuJ in twocowjoe Of a system- 
simulation, it will have to be resolved. (We are not co nc erned at the moment wfcetiier this is a free 
choice or a constrained choice, or possibly a combination of me two.> RwoMng «he choice is 
equivalent to selecting one of the aternatives in s\ But setsctmg an event in # is equivalent to 
specifying the modes that cover the remaining events in s*. (Given UK**-M), we-caii determine 
WM and thus #.) Therefore, the information gained is going f*em / to one of the events in s' 
resolves the forwards choice associated with*? No«* mat when #* the only ^Ite^ative' in s\ 
there is no choice to be resolved and mere is no informatfcMjpttned. 

For the case where «•*, everything is reversed. We are now dealing with Ha** backwards 
choice associated with s. Instead of (atking aboet tM Infomw^iiei gemed to going from t to #. we 
talk about the information Jest in going from « to $. That mfbl i ae i Ion l o u l m ti nt backwards 
choice assoc ia t ed with s. It Is what we would need to %ecfc up' fiom Stale * to one of the events In 
# «. 

4.4. Resolving Conflict 

In the preceding section, we looked % the fefcttenitrty b e tw e wi <he taforroatton content of an 
event and the information content of a tingle precondition (peetoondttlon) of the event We now 
look at the relationship between the information content of an event and the combined 
information of ajl the event's preconditions (postcondtttoiu). 

From CoroHary 4J, we have the foflowing 

• hV* ,*:■/£*, t%l-**t&*4*'r » • 


Property 41 VeeE: 

I('e)cl(«) and «t-)sKf) 

The information content of an event ojnteins th« combined information content of 
the eventrs precondttions (portcondtttom). 

The concepts of 'information gain' tnd 'information leu' at an event foflow naturally. 

Definition: ForecE, 

I^e)-KeH(e7 <a> 

r<e) - I(eH(e*) (b) 

I^t)U the infornaasaOMl»t Event e. 

He) is the information km at Event e. 

The Information g»in (lots) at Event e is lie inrcrmajton oontent ef e minus the 
combined infuj motion content of ct precBneBttini^neeleinnwons^ ■ 

In Tables 4J-44 we Hat the information gains and knee* for 4he event! tot Figures 41-45. 

^^ 1 - , L.._. ., . ■ 

Note that these tablet are entirely consistent with our remarks hi Section 4.2 

We can think ef information gain as inf ornwiion -that entere a system from the system 
environment, and we can think of Information losi as iitf ortratftm peawd f font the system to the 
system environment The significance of Information gam and information loss ttes hi their 
relationship to conflict 

The term 'conflict' has bom applied to the sftuatten in which two events are concurrently 
enabled and have a common precondition. Such a situation is shown m Figure 4.7. But for the 
class of structures we're dealing with, (forwards) conflict can arise only when two events have the 
same set of preconditions. (This is catted free, choke. ) The reasons f Or this are as follows. If two 



.J-*-v K?.7i: 

I (•) I (e) 

r(e) fie)' 












■ +« * 



0. ,,, 




Table 4.1 

.•'• Bit -Pipviia**? *-i ■■■■- 
Information Gains 


' -<> 

» ::^ ,, 

f^tk^-j;..; , 3 


<*•■:= *$%'; « 


;-..-*■ .. 


ys;'.»ii- ■»! 



, * 



S.** fk.¥~\.& 

,y.#: , ; 


:>. ■■■' i,K^ *i^ :, V :: y^-Si ::■■■■'■ . - 

Table 4.2 
Information Gains 

p ''-■> kSll 


I (e) I (e) 








































Table 4.3 
Half Adder - 
Information Gains 
and Losses 

events have a common precondition, then they mat beting to the Mow meeting. By theorem S.4, 
each event selects exactly one state from each moot tmk of that meeting. Because each link is 
contained within a 1-token state coMpemnt (* pnrft no two statet in the same link can hold 
concurrently. It follows that if the two events arc to be enabled conc ur re ntl y, then they must have 
the same preconditions. As a result, the tttutaon d e picted m Figure 4.7 cannot arise. However, the 
situation in Figure 4J can. It should be noted that ■ mjtha u j we've said applsss not only to 
forwards confMct but to backward* conflict, at wet 

Figure 4.7 


Since in our theory forward* and back w ards conflict coincides with certain structural 
configurations, we might as well define 'conf tet' m nmaursl terms. 

Definition: Fore^cE, 


We «iy that e 1 Mid H are In forwards fflftfltt*f ^^^ Weiflrthatej 
irKJ«,>rtin btdLWM^coBnkt tff ■ 1 y'» t MiAt 1 ^. (We do not say that an event to 
In conflict with Itself .) 

Property 4.2: x**" ' X" **• •ojuiviliiKi relations en E. 

Definition: The equivalenct dasm of X + we called foryirds conflict classes. The equivalence 

CIUMI W J[ MW^jW^. jjpjj |)ff|yf l3 Blm|JJPJ**r ■■■;■■ 

Property 4J: VeoE, 

The forward* (backwards) conflict dan 
alternative daw ■isociawd with «.' 

owpB^H^BaBi^Biw ^»w»ee ^ •• 

within the 

In Tables 4.4-4* we tat the forwards and backwards conflict da** for the system nea in 

figures 4J-4J. 















(a) Forwards (b) Backwards 

Table 4.4 Bit Pipeline - 
Conflict Classes 


■» . 















(») Forwsj<U 

(b) Backwards 

Table 43 Cireulatin| Bit Pipeline 

Conflict denes ~~ 


















Wt now HuMUk the 
and the rtttttonaMp 

ft* and fqnwrdf conflict chum, 


II ¥wdE. 

tijy" * T t i pf of 

Proof: Wt provt Pwt (»). 





Thoonm 14<a)fc(b) 

• . ,.-,....£„. ..)„-,. 


Theorem 43; ¥#•£: 

The information gamed (tort) at Event § U eaual to tht Mt of mote covering thoN 
events m towards (backwards) conflict with «.' 

Proof: We prove Part (a). 

r"W • K*HC«) definition 

- Ke>- JL£ K*) definition 

- Q (K«)-Ki» DeMorgam's Uw 

- Q ffld'-W) Theorem 45(a) 

- UK, Q <*•-«» Theorems 

" W{ ri*t i>W B ° 0k,n AI ** ,m 

-1Rtt»L*-{«}) Lemma 4.1(a) 


The reader may verify this theorem by comparing tht information fains and tones in 
Tables 4J-4J with the forwards and backwards conflict classes of Tables 4.4-4.8. For example, in 
Table 4J, we see that the information gain of Event 1 in the bit pipeline is {V}, In Table 4.4, we 
see that Event 1 is in forwards confUct with Event 2. The set of modes covering Event 2 is {V}. It 

We note that when an event is not in forwards (backward!) conflict with any other event, its 


information (Ion) ti miH. Thus, mfu n ntUon fc gamed (tost) at predseh; those points where there is 
forwards (backwards) conflict Furthermore, the Information gamed or fast in a conflict situation 
specifies how the conflict is resolved. TMa is bicami sstsctlng an event la a conflict data to 
equivalent to specifying the modes covering the remaining «▼«*• ~fHw& either em we can derive 
the other. 



&1 Event Graph* 

In Chapter S, we showed that «ch system simulation is isornornhic t© a simulation of the 
control structure. Since the control structure is an event $raph.,any ijwulu w obtain for event* 
graph simulations can be applied to system limufettoov ThU to fortunate becawe event-graph 
.■,*■■ simulations have some very nice properties. Those properties are Hie subject of this chapter. 

Before getting »»■**> "wb, we must introduce some rwxatiw and term in olo gy . 

\ Definition: For a directed Graph C, 11(C) denotes the paths of ; o) 

Definition: For a path p in a directed graph, 

> denotes the initial endpoint (tail) of p 

I the terminal endpojnt (hod)af # 

Definition: If * is a path in the directed graph G, and x is a vertex of G, then, 
xcji iff x appears mm 

Definition: For paths at| and « 2 * n * directed graph. 

* We're repeating the definition of 11(G) given in Chapter 2. 

Definition: If » Ui path In the directed graph G, end AHasetof verttoeiof G,thcn, 

|»| A denotes tht number of tiw Mr Hmmu of A appears in *. 

If <N4> it an inttialUed event graph, and»lsapethinN,thenki(iis called the token 
taedine* on «.. 

Definition: A circuit Is a path whose two endpotnti ate the same, An fJpiaSM ldEglil t,lt c * ftutt 
' ' tti S no «eim to encenin** mo* Jwl T e ^ ^ ' 

fj(0) denotes the drew* of 

fltyji denotes the etMMMuf dreeto of 

Definition: In an tnttafttad event graph, a Wat atdi » t dm* «entaWnf no initial 
conditions (no tofeans'X A fcejfccfegg * '■* * tmm *t «itw« eoiilaininf eaactfjr one 
Initial eendtten (enpettf ene WeaV^ 

5.2. Paths: 

Many of the ideas in this chapter folate tepadM, the eeJhi mows* avephs and the patha In 
event-graph simulations. Wc befin with baik ctrcttlta 

Property &k In an mtttahsed event graph, the be* dree* and the t-esken Mate comp o n e nts 

estioe\ejh44tfn l 4tt 

This can be seen from the fallowing . 

(a) In an event graph, each Hate hat exactly one toe**** arc and otic emergent arc 

(b) In a state com p onen t , each event has exactly ene incident are and one emergent arc 

(c) A state component is connected. 


When an initialized event graph U covered by basic circuits, we know from Corollary ZS 
that in each simulation of the event graph all instances of the same element are totally ordered. 
We also have the following lemma. 

Lemma 5J: If Z U an Initialized event graph covered by basfc drcutts, 
I U the set of initial condittojutof Z, % 
C is the causality relation fotf liimiteuen of Z, 

then for «x 1 ^ 1 >,<x 1 nj»eC, 

n 2 «4i} ^ * x dl 
nj-nj+l «- Xjcl 

If there U an elementary causal cpu#tten leading from Instance <*!*!> to Instance 
<x 2 ,n 2 >, then n s -n t for xjeS and igmfil for x&V 

Proof: From Theorem t***%i*» **mtj& ******* *k Ih4h**«im graph f or Z, and 
therefore, must be contained tn a basic circuit of Z. The image of that basic circuit in the 
simulation associated wtti C is a single strand (Cowilwy W » *Mch <x lt nt> and <x*n t > 
are consecutive instancll Tnt^itrii^K« t^itfl. ifU O W v fh« IttM beginning 
at the unique initial condition of the basic ctecoft. Since the instances of each element are 
numbered conserve!* the i number of an. instance tad*t strand todicaw which cycle the 
instance appears ft. TWlniuYfflnlJrlflfM^ mtmn^tnmffm wii*w<i*»»ing 
of the tnl^Uondttion umm^SilMmmi^ ^ ^ ■ * ^ ' ° 

In Figure U is an initialized event gfapl%&%ered bf bit* ctotutti IiiflguwWfli » Emulation of 
that event graph tot which each hotting of in to*** €**&* ******** dashod <*** 
Notice that instance numbers are in c r eme n ted by 1 at each holding of an initial condition, and that 
they remain [the same at all other Instances. 

FlfunS.t InlttallnH Keent 

of LemeM 54. 

Theorem 64: If Z to an i ntt ta tyi ietf ej|an|j^^4a!fl|l)^ 

T ii tin mi iif InliU) uiiliitiMH i| T e , .' ' 
T to a stamfcttafi of '% thin, " 

If # s and * t w« paths (causal 

to T having the same 

then the 

Proof: Let , r 1 -*r x -<x^> and rf-cj'-^/o. By Uraim 54* |hi 
conditions crowd by both #} and r t U n-tn for x*I and 


r-ohI for vol In either caw 


As an illustration of Theorem 54, consider the foHowmg two paths in Figure 52, 


V <a,0/ i 





<b,2>\ «c,2>.^; <t,i> 



«a,3)/; <d.2>% (<e,2>« X , 



4>,3>\ (<C3>/) <f i2 > 


f <£ , 4> fj <d , 3>\ (<e , J)*) 

(<c,4>/} <f,3>V 


Figure 5.2 Holdings of Initial Conditions 


Since #! ami r x hive the same endpoinu, their images should have the lame token loadings. Let's 

^-^Ib2alb2d3 and Uj| r 2 

» 2 -2dSf4e5f4eS and lfyj-2 

It checks. 

For an initialized event graph covered by basic circuits, the next theorem establishes a 
special relationship between the paths of the event graph and the paths of a corresponding 

Theorem 5.2: If Z-<N,I> U an initialized event graph covered by basic circuits, and T is a 
simulation of Z, 

then VmcIKN): VrdI(T): 

>-> A *•-** A lMh-Wl * ErdlCT): >V A f V A f- M . 

If M is a path in N and 9 is a path in T, and if the endpoinu of m and 9 are the 
same and p. and 9 have the same token loadings, then there exists a path in T having 
the same endpoinu as 9 and whose image is *.' 

Proof: Let V-ce^n^ and **«<x 2 ,n 2 >. The required path f can be constructed by backtracking 
from <x 2 ,n 2 >. Property 25 guarantees that at each step there will be a way of extending 
the path in accordance with p. There's one exception though, and that's when a holding in 
the back boundary of T is reached. By Lemma 5.1, when a holding in the back boundary 
is reached, the token loading on the path already generated is n 2 . There are two cases to 
consider (1) oc^np in the back boundary of T and (2) <x^ x > not in the back boundary 
of T. In the first case, Wr-n 2 by Lemma 5.1, and, therefore, the path must be complete 
(otherwise, we would have Mi>n 2 and Im^Ii)- In the second case, Wi<n 2 by Lemma 5.1, 
and, thus, this case cannot arise. So we've now got a path f such that f '-<x 2 ^i 2 >»e > * and 
t"H- Because *jt-*}, *f must be an insUnce of Xj, and because |pli-Pli, lfli-1% From 
Lemma 5.1 and the three factt (1) >V, (2) fJrPli. Mi < s > '*"'*• ll fo,tow * thtt 'f " v D 


To illustrate Theorem M, we consider the foHowinf path u in the event graph of Figure 5J and 
the following path r in the simulation of Figure W 

u - 2alb2»lb2dS 

9 - <24>«Ux34><f JxilxeJJxS^xf 2><*2><**><S*> 

We have V-V-2, u'-f'-S, and lpfc-Wi-2. Therefore, there should be a path f in the simulation 
of Figure 5.2 having the sanie endpotets u r and such that f-n- Therels. 

We now look at the circumstances surrounding the ordering of two occurrences in an event- 
graph simulation The ftrst part ot off dilt miiwi l i appsMuh ) *» ■* Pmti net sim uh rtofi t, . 

' Suppose that q isan uuurienor ti a im^ulauo^ Tt sui w e e rt iep > a ^ l lw ^the? oa»rro»c«« 
Into three categories: -&wm that tfjOjgi f fcHhoei tfs^fiiB^s^ 4 #hliiii^,ltipt *re 

\ A ' 

'.*■ ":'.: r '...'..',i^-~. 




. .,:-lH , e«Ojdifif«i U'- 

: ' ■'■■::#*■ 

.-tk . ..- .. 



occurrence* \ / 
concurrent with q / ^ 

■ ' : : ■■■■•.< 


, . . - 

/ \ 

/ \ 


otcu i»fo«ee» 

... ^ 


Suppose that the occurrences of Event t are totally ordered in the simulation with f 






i >¥■■ 





\ / 
/ \ 


octurFFintis of 












Now if Ms aw otarnmnx* Xwt * o so a o dmg v»H B J*»«* oyi«»».|^t^ integer * such tb*t V 


occurrence eT I vem # i>reotf*ng q, b Wgtlw !%#»# 0» n^ Joft HMwpgor^*^ ' 
preceding <S3>. while <U>Uth«^oceurr«KerfEv«mlpm«Wiif<S3> ^^fm^^^ff 
to occurrences of Event * foBowing a. 

We know that In t simulation of an event graph covered by basic circuits, alt instances of 
the tame dement are totally ordered. W# woo* mm Mks to determine f or such a simulation under 
what condition* it Occurrence <*i«ni> the Vth occurrence of Event « t preceding Occurrence 
<« 2 ,n 2 >. To do that, we need the concept of 'synchronic defer*- 

Definition: For a path a connecting two events in the inWalHed event graph Z-cN4>, 
*zOs) - Wli - min{irii I WHN> A '»» A fiO 

'l^n) U the token loading on '"* minus the minimal token loading on those paths 
having the same endpotnti as *7 t^a) is the sg|$agcje& of p (with raspoct to ZX 
(When Z to understood, we shall write the swxhromcdelty of pu Just IU>) 

.. 1 1, ':>■ t^v«*^/5£ "'-;■> 



We give the synchronic delays for several of the paths in the event graph of Figure SI 
9 X - Ib2d3f4 W»i) ■ 0-0 - 

* 2 - 4e3c2al ««r 2 ) - 3-3 - 

* 3 - 2d3c2al 0V3) - 2-1 - 1 

* 4 - 3f 4e3 KvJ - 1-0 - 1 

* 5 - Sc2d3f 4e3 9(9$ - 2-0 - 2 

In the special case where p is a circuit, the minimal token loading between the endpoinu of 
p is 0. We thus have the following property. 

Property 52: If Z is the initialized event graph <N,I>, then, 
VweO(N>. ty^-bk 
The synchronic delay of a circuit is equal to its token loading.' 

The following theorem says, in effect, that the synchronic delay of a path cannot be 
decreased by extending the path - the synchronic delay either remains the same or increases. 

Theorem 5.3: If m and j* 2 are paths connecting events in the initialized event graph Z, then, 

M1SM2 * *zO»i>£'z(M2) 

'If mi i» a subpath of fi 2 , then the synchronic delay of m is less than or equal to the 
synchronic delay of 4*2' 

Proof: Let p 2 - ft^f. Let ¥\ be a path of minimal token loading from *Mi »>i # - Let '2 ** a 
path of minimal token loading from *pz to H We nave < 

«z0»i> - Ml " *& 
and, t^) - Ml " *lk 


'.- ■**je<;*3: -*#*R s^q&^^r^P^i" ' 

jgi- Sshajv*** 

Thus, i^j) - n, ♦ tod ♦ Hr j »& t *> 

Because r s to a path of minimal token 
loading from *m s to uj*. 

►ill * IVhk**- <*> 

Combining Una (1) and (2), we get, 


We're now ready for the major result of tMS MCtfcm. 

-• ■ • . ■;;;■ -^ f '**■*"? ■,■•■■■ ;V«r-*i,-7-:- -*>^-<t •■.,- > ... ..., v . / , 

Theorem 5.4: If Z to an initialised event graph covered by baste circuits, ...... 

TtoarimmationofZ. f ^-«^ ■ • 

<t,/il» off jf^nj? a» r oo^irio»p|. te T v , _ ; ,^ ; ^^ ^ ^ , . 

then the following are equivalent 
(a) «|/ii> to the fc\h occurrence of «i p r todl o f ^n^" 
'(b) <«,*!> to *o toi ocoirrwce ofV, fbi6w^<» 1(n > *» ?^'- > <• 

There exists a path from «*•*!> to «»»»♦>♦ and the wncl i ron o n te delay of its imago to 


Proof: We prove that (a) ^(c). It follows, by symmetry, thaHB) «*«. L*2~*U>. 


Since <fjji|> U thei^txainoattof^ iisowriiM iii|ny rii^th^must be the 
tost Let #i be a path from «\#i> to «»g, nj+k-b, and # s a path from «f|, n t <*> M> 
to <*j/ij>. (A path always eatoto between ordered qoomvojioss? v 

■ A* 


•<e,,n 1 > 

► k occurrences ofei 

<«a n a> " 

Let r-#i*#> and tot |i be a path in N frwt «i te « s swefc chat ez(si)-0- The 
(wrifmion or tyntiiiuMiiiL atwy gifavav - ^■■-^■■^■.-■■-- 

From Lemma 50, we have 



We now show that Wfrtyt Since *zUK t^^i. Let HfyrWi. and tat « be an 

(Such a circuit exists because Z Is covered by basic circuit*.) Let ji'-e*V*' a)' is a 
path in N from «i to «j. 

fc'li - «*Wi - Ni 

Since *' and *j have Mm ...seme endpomti (#j and <j) and s»'IH*ili' Theorem 5.2 
implies the existence of a path | in T f rom^^irt|%4> to <^n s > such that fat'. 

Because f-w*ji and «i*w, f will crass a occusWnces of *i after leaving <#|/i|4k-l>, 
and before reaching <»^n s >. But <#i/i|-«k-&.>is the bat o ct u t nance of #| preceding 
<«2^i>- Therefore, we must conclude that a-0 and, 

From Lines (I). (8). and (S), we have %(*H-1. 


(0 * (a) 

Let p and m be as defined in the first part, and 1st */ • eA'V We get. 

* M a means that m is repeated a times. 


Theorem M impMei the existence of a fMth f in T from <fi.ii!> to <*j,nj> such that 

f - m' - e^'V Let f • flffl whw * f 1 • e^" 1 «*» *l " »• fi *» a path in T from 
«l^ l > to <i v «|4- »-!>, whik fj to a path in T from <*i. n x * krl> to <**n 2 >. To 
show that <# 1( *i+W> to the lyi occurrence of « t preceding <*»**>. kt ( be any path 
in T from <#!,«!+ W> to <^aj>. By Theorem H 

But since f| • fi and IjOt) • % 


Suppose that ( contains an ossiiBpi^jaJt^-s^.^i^s^Ari^.^ffll^ be the part of 
( preceding that occurrence. | t to a circuit in N fbogftnning and ending at «,). By 
Lemma 5J, fill >0. m other wordf^l eflllii^^^^ 

than a But this to inconsistent wtdi Line (0. We mutt conclude that no path in T 
between <* v «,♦ iW> and <* «*> «i«yni^-i»iiM4in»^4fil*ir <* t , n t + k-\>. 
Thus. <#!> n t + IH> to the tost occurrence of #| |n e tedtn| <# t a 1 >, and <*i*%> to the 
Jfth ocuii r e nte of #} preceding <*»*•>< ^ * D 

The equivalence of Statements (a) and (6) In Tfteerii'frWb* etoualtoedlis nr figure W 


k occurrences < 
of e a 

> "k Occurrences 
of e<| 

<«i ri, ♦ fc-i> J 

<e 2 ,n 2 >J- 
Figure 5.3 Ordered Occurrenced in an Event-Graph Simulation 


In the simulation of Figure 5.2, we see that <24> is the second occurrence of Event 2 preceding 
Occurrence <13> and that <\fi> is the second occurrence of Event 1 following <24>- We have the 
following path v connecting <24> and <1,3>. 

9 - <24><d4><34><c,2><2,2><a3><W> 

*-2dSc2al and <(»)-! 

The theorem checks out 

5.3. Cones: 

Because synchronic delay is not a convenient concept to work with, we introduce the concepts 
of 'back cone' and 'front cone'. 

Definition: If Z is an initialized event graph, 

N is the event graph associated with Z, 
S is the set of states of N, 
e is an event in N, then, 

+ z ~(e) - {seS | IpentN): >s A sep A *»*-« A «jt)-0} 

> z ~(e) is the set of states s such that there does not exist a path of delay zero 
beginning at the input event of s, passing through s, and terminating at e.' 

+ z \e) - {seS | lj»en<N): * M -* A se M A $y A «(m)-0} 

> z "*<e) is the set of states s such that there does not exist a path of delay zero 
beginning at e, passing through s, and terminating at the output event of s.' 

4 z '(e) is the back cone of e! and e^e) the front cone of e. (When Z is understood, 
we shall omit it as a subscript of +.) 

The two definitions are illustrated in Figure 5.4. In effect, what se«> z '(e) means is that the 


Such a path 

has non-minimal 

token loading 

e . 

paths with 

token loading 

1 *"T--Such a path 

has non-minimal 
token loading 

<•) »€$"(•) 

(b) • €++(•) 

p&flftm 5.4 B*tfe* A0f»eA«toa4 *ri£fe M$W%p*^ : **&. Con *» 

; *f'-. 


♦ "<:?); 

4"" (4) 

abode f 

>n uj^aa 

•*■ jM* 

sjw* 5^y . yfw 


lirlli i Um> 




b T-t'? » 

jji i^aa 


a b c d e 


♦ T (2) 
4 + (3) 

it|«! Nw* "$#-J WW ^5»# 


1 w 

(fe-r Innsj 

•*-« **-* 

i~i' ?*0f^ 



(a) Back Conea 

%{&),. Front Cones 

Table 5.1 Characteristic Functions for Front and Back cones 


'quickest' way from the input event of s to e is not through s. Similarly, what se+zte) means is 
that the 'quickest' way from « to the output event of s is not through s. In Tables 5.1(a) and 5.1(b) 
we give the characteristic functions for the front and back cones of the events in Figure 5.1. Note 
that in our example, 4z"(e) is the complement of ^z^e) for each event t. This is not generally the 

The significance of front and back cones is best understood in terms of simulations. (The 
first part of our discussion applies to all simulations, not just event-graph simulations). Suppose 
that q is an occurrence in a simulation. The occurrences in that simulation can be separated into 
two categories: (1) those that precede or are equal to q and (2) all others. With respect to q, these 
two sets form, respectively, the past and the 'not past'. Now between the two sets of occurrences 
there is a boundary, and this boundary is associated with a set of holdings. These holdings have 
the property of not preceding q but of being initiated by occurrences that do. This is illustrated in 
Figure 53. If we imagine the simulation to be three-dimensional, then the boundary resembles the 
surface of a cone. Similar remarks apply to the boundary between the future and the 'not future' 
with respect to q. In this case, the holdings making up the boundary have the property of not 
following q but of being terminated by occurrences that do. This is illustrated in Figure 5.6. In 
Figures 5.7 and 5.8 is a simulation of the event graph in Figure 5.1. We've indicated the T>ack 
cones' and 'front cones' for occurrences of Event S. Notice that the simulation is 'sliced up' by the 
'cones' of each type. 

The reader has undoubtedly noticed that we've used the term 'cone' to describe both sets of 
states and sets of holdings. The correspondence between the two views is straightforward: If q is 
an occurrence of Event e, then the holdings in the tack cone' of q are holdings of states in ♦z'(e) 


occur rences 
preceding q 

holdings not 
preceding q 

Figure 5.5 Boundary between Past and 'Not Past* 


















\ 5^ 


holdings not 
fol lowing q 


v ,. 

fol lowing q 

Figure 5.6 Boundary between Future and 'Not Future 


a • 

1 •: 

b • 

c • 

2 > 



/ a • " \ d 

e • 


1 •: 




2 >: 









d •, 

e • 









\ 3>: 


C • S ' f V I 

/ > 

e • 

f a •' \ d 

v \ 

\ s 

\ \ 







v_ ' 

e • 

Figure 5.7 'Back Cones' for Occurrences of Event 3 


a .• 

1 •: 

c • 

2 > 


S N 






a • / a * / \ e • j 


/ \ 


1 •: ' 

/ 3/ 




f ^. 

a „• ^ d % / \ e • y 

2 >: / 


1 • 





/ x *-' 

3 V 



b T • / c • 



f • 

/ N 

2 ;•: 

/ . 4 > 





d • / \ e • 


f X 

e • 

Figure 5.8 'Front Cones' for Occurrences of Event 3 


and the holdings in the front cone* off ere homing* of «e*s incite* Thue, m see that in 
Figure 57 each holding in the "beck eone'of wi occorrenm ef Event B to * holding of » state In 
4'(tht*fiJt). Similarly, weeir thst to Flguie 18 mew h eel in g In the front cone' of an occurrence 
of Event 3 to a holding of a Matt In ♦UMM^ Then Ideas aw eKpce»»«l to the f ettowing 

Theorem 5Jfe If Z is an InittoJtocd event graph covered by bask diwto, and <H,O.C> Is a 
simutotien of Z, then f or <vr»cH and <**>eO, 

<s J m>i<e,n> A (3f eO: f •*s l m>Aqi<a«>) • *«♦«<•) *** 

<eji>i<im< A (3qeO: <wn>«qA<W>$") *■ se%^|# <°> 

If <*m> doesn't precede (fotew) <«*> but is Wttotod (terminated) by an octurrenee 
that dees, mens must k*i*dmk1hm*mi*& '*' ^ 

Proof: We prove Jutt the f bit litJf.tNiem^ 

Let q - <*'*'>. Then q must nemmvtiy be the lur e*wrenee of <#* preceding <**>. 
because any later oocnmmm of «' would have to follow <s,m>. (<wn> must be terminated 
before amther hemmg of sulnmased.) By Tl. teliOl w/ m«^ eete» > path * from q to 
«*> such that *z<#>-0. Now, tf them existed a path a in the event graph swcJt*tat >*'A 
s«« A «*-# A KeM then by Theorem 12 mem itfm^vitebe'ipe^ 

event graph eiUsts, An m»ed7*(«). ° 

We new relate the concept of cones to the .Idem, to. the preceding section. Consider the 
following observation about me Umuktfort *i Flgum 5>. If q is an oemrrence of Event S, and If * 
to a path originating at an occurrence «*> and termtoattof at q. then «mi> to «he irth occurrence 
of # preceding q iff * creemYltf "beck cones'. For eeampk <U> to the fourth-to-tost occurrence of 
Event I preceding <M>. and each path between the two occurrences crosses e*actt> mmck cones*. 

A similar observation aoplto to d» Yrost oaatlA * Jtfo* ffe, $>«?* Ift oj|a*piP* * **««l * 
and if # to a pa* ortojMutoat; at o, m*mmH*#*>*m mmm* **#>>$** «m> *•$?$* 
ooamonca of # faUovteg q Iff o o*»« H fro* f^ ^^^ the 

Theorem && If Z to an initialled event graph covered if •** etooalto and » to a path in i fiien. 

The synchronic delay of * to equal to the nomoor of tome) *• bock (front) oont of m'i 
head (tai0 to creaifcif .. -f., *,. . v -j« 

Proof: Wei prove Port (a) brto4«e»Me»tole»jg**** . 
For loK we have ftpX) and W^'^*)-*- 
For the Induction Map, It to oaff ktont to than) thai onoa .a to 



tfe) if^iO 

V* Hs 


vtOinotnMg, we gee, v 

«P#zKm"K For thto qua, there cannot «tot a ft* eojftnntoM at *m umtal n lna, s, endinf at 

■■' ■*-^' - <-• , iu* r, , jrf* -*■> „?$# k |;*9 Wjp Se ,«i£> inl^^. r . 'nasyj . 

n , ana wnoM aoiay n xero. Mcaaoijf: nat ma nm moi propartnv, imw do max 
KsfV^O. Thto toaoltoi ttat ffWktb. or oMtvotootlr. 


MiHUrlfli*! : ~ ■ ■• ■ » 

~ >:■■'■■ ■ : ■■ * w . ■■ ...■""¥■' 

■■■.,:, ■ .. ; ; - , ■ ^-. ;- n ^;-./ : >'. > ^ i' ■ " 

B7 hypothesis, there wilts a bMfc dratt flontttolff •** ». This means there's a 
path from V to > with a token kwdittfof t«|^ Wopatl^p^li i»afptnd«l to tht 

tall of f, we get » path from > to r* with a tokan loading of 1-WfHTh- Since { is a 

path from > to p* and K$-0, 

From Lines (2) and (S) wo have 

and from Line (1), 

*eV<*> For this cast, inert «tfef»* pHh bogmnmg ft, ,*» » ? "»» ? *r » *#** * »** «"* 
whose delay is tero. Since |V|, {\*\ and KD-0, s| must be «sch a path. That 
fiwani- that ^ end f ha^ tfw «ne ea#em» onrl <io same dotty (seroX Thus, 


From Lint (IX we got, 

IfcHoW D 

As an illustration of Theorem &A, consider the pa%*f { lMMIeynNilie]Pnr«UvWo have, 
eW-2 ■ 

>-3 and p*-4 
♦VMw) and ♦VjtHb/UJ 

Combining Theorem M and Theorem 16. we get the foNgpJng corolkry. 

' ^^^^^e^^^f^^P^^jf^!^^^! 1 !^. '''-'•- -•* 4 "" " '. V***:* ■ 

Coronary 54: If Z U an miUaUxed event graph covered by bask circuits, 
T is a simulation of Z, 
- < <» t , nf> asst o j o> * y. s * » oesetronsm in Tv ■ 
. ofcen th*£ofawiM stfe esin>ah*K* 

(a) <*i. nj> is the *•* occurrence of I, jiteoiaThf <** *,> 

(b) <tj, n x > is tht Jkth occurrence of #j fohowtag <* t , «|> 
(c)3rtII(T): V-^np A r *-<# 1 jj> A *e(#)-A-I 

*,..■.;■* ,v-., -. ».*■,■. /V* ^,,.> ."■;--■■. 

^'-e ■:-:,■ - S-v- -..-..- $2 *£ M- - 

There U a path from <«|,»i> to <V4> and the synchronic delay of Us image U k-L' 
(d) 3rtII(T>. V-et} ji|> A e'xf^a|> A HtVfcj)- *"* 

There is a path from <tift\> to <****>, and its image cresses the back cone of « s a-l 

times/ H! -'- s * ^->* 

<e) 3*eHff* ^"t-«i^i> A # # ^oj|4iji A^^ff^ 

K" , ' TZAlZ 01**. > , .A. " ' 

There is* psnh from <» 1 ^ to j^* «M *o imajs ssostes the f |«nt cone of «, a-l 

The next two theorems provide us with some useful properties of cones. 

Theorem 5.7: If Z^4> u wi mitiakied event grip* awered by t>^ 
E is the set of events of H. men, 


Tor any event #, the token loading en a dree* is equal to the number of times «'s back 
(front) cone is crossed.* 

Proof : We'll prove Just the first equality ,■.*.» 

Since N is connected and covered by circuits, it ^sfrfagiy Os pn o Qd Let.jt be a path from 
'•» and ei* to «. Thus, J(*) - and p* -#. Consider me path sip* 

•z(«p) - kalrlpOi-hftr ffl 

In addition, we have by Theorem &6(aX 

: ! ^^sii#£'^ 


But W^,)- ##*)««. Thw, 
Front Line* (I) and «> we get. 

Wi •*%•<«) 

• e 

Theorem 5* If Z-<NJ> ii »n littt i ilh i d twwt fayli w i c i i faf fcwto dfotto, N is ^onn nottd. 
and E U tht Mt of events of N, then, 

If two paths have IN same endpoints, then the difference In their token loadings is 
equal to the difference In the number of times they cross A bacMf root) cone.' 

Proof: We prwe the theorem for J««t the fint •oualtty. 

Since N it connected and covered by drcuto, It 
from pj* and Mi/ to >i hod >|. By Theorem 17, 

o»lll + l»ah - «»lle>-«eV*>»«e>-W) 
Combining, we get, 

Let n, be a path 


^1 j 




5.4. Syfjern Space; 

mo tneory ot mwmi can 
introduce in this section a nouen of 

and time We 
•****» notion of 'system thne'. 



Suppose that « t and «| ara awn* in an t nw l st l wd aym fra f h wrgatf by bade drcuta. In 
S action 5,2, we Isamed that In each skanktitn of |he meat gteph the oi dating^ |njdjng front 
occurrence* of <| to occurrence! of f| aia at shewn to fl|iiwji|(|n n yljlh o, onf o r i n g*4o*dlnf from 
occurrences of ..a*- to occwTOMas of «| inu ihew* in Pleura 8J(bX Tha auatftan now is this: 
How do w« combine tha two fifttftt to fat Um < 
Of ^and*^ 

*^sf? r H %< :,<n*«'» te 

<a,.m t > 


<e1.n1> 1 

<o I .m I *2> <e v n,*2> 


<o,,m t »3> <Oi,»^ 

<e„m,*4> <» 1# n,*4> 


Figure ft. t Ordering} 


aynHirano* ohohno ai a 
d e termin e s *ho# far alfeed 4 emanates* fat 

tht ,ilBd^ intvMn:rii^>iifaBii In an eaen>]graph. It 


Definition: For Events « t and « s in the ttrongty-oonimimi viwt gjrnph Z-cN}>) 


nrin{|Mii I inO(N) A ^jCm} **i"t 
*PA*\*$ 1* the minimal token loading on s h ow drcusts contatoiny both « t and « t .' 

/%(*i/2> " 

understood, we tanefly omH it as a subscript of *) 

In Table 52 we give the synchronic distances between the events in Figure 51 


12 3 4 

12 3 
10 12 
2 10 1 

■ ■■ 1— * * in— ,m m 1 

3 2 1 a 


p(e 1 ,e 2 ) 

TebteS.fc Synchronic Ototanees 

The following theorem provides the connection b e twe e n synchronic distance and the 
ordering relationship b et w ee n two events. 

* This is equivalent to the notion of distance Used by Commoner ti3| (See pp. 112-06) 

K^^^jr.";- ■ ^#~^ 

Theorem 5A If 2 1* an 



vi«m fl^ni ^WWWI OfHK ONNI MO lUONgiy 

end <t|^i» ««miM in t\ 


<e a ,n a >»; 

• <«i.mi> 

<# 1 ,m,»p, («,,*,)> 

By Theorem M there exists a path «, from <*},»,> to «,*,> and a path from » x from 
<*!,n 2 > to ^ such that *#,).« and fl^-a Let Z - <N,I> and r • eye> Because 
#1 is a path from «, to «, of mlrift^ tefcaa lead** and I* it a path from «, to #, of 
minimal tokon loading, » mart have mtntojet Man leading with respect to thaw draita 
oomammf both a and * In oehar wd». ^ - ^, *,). atom* to a path from «,^>ft 
<»l*l>. we have,!* Lemma Utnttft,^.||fc. The deM resot foam*. D 

We see In Figure W that <U> Is the jfe occorrenca of Event I preceding <S4>, and <W> to 
the next occurrence of Event i fojewjnx <34>. The difference in occurrence numbers of the two 
occurrences of Event 1 Is 2. This Is the synchronic distance Eventslandl 

With Theorem 5.9, if we have an initialized event graph satisfying the necessary 
retirements, than we can determine the ordering relationship between occurrences of two events. 
AH we need know is the synchronic distance between the two events, hi Figure 5J0, we show the 












o ^ 

ii o 

*•* ii 

u V 






















*', ij^ffi^fig^Rj*; 

Th« next theorem iMM that p is a men* when Km event graph satisfied two elementary 

Theorem U0-. If Z is an takialiied event graph that U 0>*rongh; oamajaad and (2) frac of blank 
droi**,th«n^toam**antfnt*af«*w«i i ee rtfl cj n>, far events^, eg, and »> 

<b) ^rf«i^i) - 4rfVl> 

(c) /■fcW-'s) £ ^i<M^ 

Proof: First of all, strong comwetivitr guarantees that ^ is watt defined. Property (a) follows 
from the fact that Z U ftet ef us** tiiuji Fiofpiltai (h) awj fr) fatliiw duortty from the 
atftttnoR w wfmJiTomc i 

Strong connectivity and absence of Wank droits, together wife wvembittty by besfc drcuits. might 
be regarded as criteria for 'wtM f orimdn eti' in eve* graphs. Earthwork W hat shown that 
absence of bhuik circuits and coverabMity by basse cheat* are necessary and suf fsdant conditions 
for liveness' and 'safeness' in event graphs.* 

We now relate the ideas of this section to the theory in Chapter 1 Theorems 3.3 and 3.8 and 

-■■ <: ' ip 

Property SA state that the Wttattaed control structure k a strongly connected event graph covered 
by basic circuits. Thus; Theorem SJ asuftev Fttrtfuemert, we have the foMowsnf coronary to 
Theorem 5J0. 

Corollary Wfc If the initialized control structure Z* is free of blank drcuits, then <£*,^*> is a 

t Liveness means that simuhvoons of the event graph can be extended arbitrarily far. Safety 
means that instances of the same element are totally ordered. 

Definition: If Z* ii free of blank circuits, then <&*,/>z*> is called the system space. 

5.5. System Time; 

In most theories of system behavior, 'time' is Introduced as a primitive concept Our 
approach is novel in that the concept of time is derived from the logical structure of a system. We 
only require that the initialized control structure satisfy three simple properties. There is no need 
to augment the definition of a system, and there is no need to modify the simulation rule. 

Definition: An initialized event graph <N J> is said to be synchronous iff it (1) U connected, (2) it 
covered by basic circuits, and (S) satisfies the synchrony property: 

3kdN: VitffftN): IwHImIt 

The length of each elementary circuit is proportional to its token loading.' 

An initialized event graph that is not synchronous is called nonsvnchronous. A 
synchronous system is one in which the initialized control structure is synchronous. A 
system that is not synchronous is called nonsvnchronous. ' 

For example! of synchronous systems, the reader may refer back to Figures 3.13-3.15. In 
Figure 3.13(d), the proportionality constant between the length of an elementary circuit and its token 
loading is 2* In Figure 3.H<d), it is also 2. In Figure 3.15(d), it is 4. An example of a 
nonsynchronous event graph is shown in Figure 511. 

t The question of what an 'asynchronous' system is is outside the scope of this discussion. 

* In determining the length of a circuit or a path in an event graph, we count the arcs in the 
abbreviated representation of the event graph. This reduces the length by a factor of two. 

Figure 5. U A Nww ynchrwwm Event Qtaph 

We consider now ion* bask property of sy iK hi eao oo ovo« graphs. Beceim a synchronous 

- • - .** <■« ^ . - •- - • -■'■• 

•vent graph is connected and obw^*t»*^ <*^«^^ ***•*• f * iDI,rt, « 

Property 5>. A synchronous evem graph to itimigh; < 

rrom ine sywouimy prwpwty, w« gw wwtowinnHSj. ^ 

Property 5.4: A synchronous event graph to f roe of blank drcuJt*. 

Alto from the synchrony property, we know that the length of etch elementary circuit to a multiple 
of k, and that the length of each boric circuit to equal to k. itfettewt that k to equal to the god of 
the lengths of the elementary drains. Now, bectuft any circuit, elementary or otherwise, can be 
viewed as the superpotitkon of elementary drcuto, the ryndwony property applies to §£ circuits. 
These results are reflected in die next property. 

< ' •" " < . "*™. 11 ■.* - - , , 


P iuu er u Ut ff xNJkii ft svndiraMutavait^afrfi. dMn. 

VimCKN): M-r(NH«ii 

To help tu In understanding ttw notion of time prssontod below, we introduce the concept of 
the 'phase relation'. The phut relation to generated from an event graph in exactly the tame way 
that the akernattvenen relation to generated from a part The tame 'cottapiing' procedure to used. 

Definition: The phase leJatten for the event graph N-<SXJ> to the minimal relation 
/J.S^SUE) 2 such that 

VxeXSUE): x/J N x 

Elements x t and Xj are said to he inohate iff X|£ N Xg. 

The concepts and results on tbhih o d toi Stetson 19 for the ikentttiienejs relation carry over the 
the phase relation; 

Property SA If N tottaeventfflts*<SJ^th^ 

'Each eooivatonct class induced by /J N contains either exclusively states or exclusively 
events.' -1. r\/- 

Definition: If N to an event graph, then those «ouivatonct daiecs Jnduced by 4„ consisting of 
states are catted Rhjsji and those assisting of ivshts'ara called phase transition*. 

Definition: if Nit the 

U the quottant Mt ft-41£>. 

Property 5.7: ft tot net 


■fkititK', .3 l 

*^i J t */ "■/*'?; ■?**&*"! 

Property SJc ft *• »* elementary draUt ef length $#f)t* 

In Figure 5J& ve »how bow the fwefeeioaftri tira*£er p ^«^^ to 

■W ..^ CUv- 

I" "I 

fa, <*,♦>, 


*bj»re.J. Q«»f*ti w n 

V*3&" £;'*■ '■-'? '■> 

The fundamental dreuit may be thought of at a fcetk'. New with this interpretation. It 
might appear that to make an event graph '•yiwfcronew', it WW be neeenary to YhV the event* *" 



This pro p e rty corresponds to Theorem 12 

■*•*•■*■ *.%v **. » «yw,V** , «JVw ( "--fi , *. - ■ 


a phase transition 'in unison'. However, this is not the case In fact, ii.wof^t even>be necessary for 

the initial conditions to be in phase. AH that's required is that the ku^l comiitioiu belong to a 

'marking; class' in which it is possible for Just those states in a given phase to hold. As it turns out, 

there U exactly one such marking dais* It Jm§ been sheW-that in * «t*prtfy connected event 

graph free of blank circuits, two 'markings' belong to the saim mar Uogetatt iff they induce the 

same token loading on each circuit Now in the *MtJW Trtwil J^ theer pritni in a given phase 

hold, the token loading on each circuit is known: 

M ' 
VsjeJMN): Mi- — 


But this is Just Property 5A which is equivalent to the synchrony property. Therefore, a set of 
initial conditions can he brought 'into phase' iff 'mespiibJia^fMBasYt^ii'atisfied. 

With the preceding discussion m backgw*ihct Wre no* road y<to flwahy <r» major results 
1101 limine tn srnftirnnfluiavont gmnht 

Theorem 9JI: If <N J> is a sync h rono u s event graph, then, 

If sti and st s are paths in N having the same endpetnts, then the length of «} minus 
<y(NMtoken loading on «}) equals the length of jig minus <*<NMtoken loading on nj).' 

Proof: Because a synchronous event graph i^strangjy mmm& t here eautt a patbug from nf 
and nj* to *«i "** Vs* From Property &ft we have, 

y»lNu 3 l - T<NHb»ili^i3il) 

• Theorem 11 in [4] 


Oxnbfciirif , we get, 

Theorem Mfc If «ff,*Vis t ryncl i r o w e oi event tuaph, torn, 

If U^ f0**»* 1*^11*01 J ••'■: .M-^ '■■-.. ftofc'* 

Proof: Beauue p^ forms & circuit, wt have bv Property &&, 
Tim theorem f onows. 

Thoorom U* If T«*H.QjG» tea iimuliHaii of ai 

In * limubiion of a l ynehfoooui CTo mrm ya y 4f,-t— f law hawa l o w m a w a miuntni i, 
then they must bo the seme length. 

Proof: From thoorom Si, we know that PtlrHtife- 8bjNt #} and fr| are both paths In the 

l ynd i i o w oni owni t i aa l i iin a iaiiH % ^hWp|»M^«y *•&"*% J* ft fotows that 

Before we can define the 'time intervar b e tw ee n two bettings or two occurrences hi a 
'synchronous i tm a l e ttorf , we meet f iret have a notten of 1e9w4n**uref whawi^the first i 
of two stales or two events are. ■***' 


Definition: If Z is the synchronous event graph <NJ>, then, 
for Events t and * z > 

dzfcj^-n iff 3»»dI(N): M-«l ^ M # -«2 A n-||thr(N)lMli 

•d^i^j) . n iff there exists a path p from « x to « 2 such that n - lnhKN)!^.' 

for States *| and j 2 , 


«zOl- 'i> - *d<V «2> wh « re «l i$ the uni< \ m 0Ut P ut event rf *i *"" '* 
is the unique output event of i 2 . 

:-* ■ 

(Theorem 5J1 guarantees that fy il weH defined.) 

dzfa*t> te,u u * ' how far ahead ' lhe fir,t in$tance * *i te S oln & to ■* with m P* ct to the f ,r * 1 
instance of x v In Table 5*. we give the values of a^/j) and afr^) for the synchronous event 

graph of Figure 5J. 





















(a) 3(e ;L ,e 2 ) 







































(b) d(s r s 2 ) 

Table U 

Using dz, we now define the 'time interval* between two holdings or two occurrences in a 
synchronous simulation. 



Definition: If <x l( nj> and ow am either two %t lj \* p m tmvmnmm m a timulation of 
tht synchronous event graph ZxN,I>, then, 

A z (<x 1 ,n 1 >,<* > ni>) - (iir^>tW**^i%Jfc> 

Aj^i4i) **• aansiSil*»« ft *tr 

W« five some samplt time inttnrali f or tht Unwhtton in Fifiiw It In this case, y<N)-& 
A(<U>.<1W • t*2«* - 1 

A(t2>,<14>) • tet-3 ** 

A(b^>,<f4>) - (-0K2 ♦« «0 

AC<a>,«^) - ta2*2 -2 

The next three theorems show that Ag satiaflei these prop o rtl ei that one wont* i 

meinc TOT QRM> 

Theorem !U4t If y 1>flt »nd ^art dther thrwhofcUatsmth rwo c otntn^ 
synenraneut erem §Mpo *« OMn* 

<W ^l**> - -A^ftf 1> 

fe> Atffi*i> - *2<fi**> ♦ Aztofi) 

Proof: (a) Follows directly from tht definitions of L z and djg. 

<W e^*,) - -dzdt^x,) by Theorem SJ2. ft foNews that ^ tf j) - *&z!tf i**)- 
(c) Let e/|*<x 1 .n 1 >, ?j-<x*«i>, ?s-<*i.*3>. and 1st I • *l, I». We hare, 

and *<«,*,) + Affeft) - (ii^hKN) ♦ ««|^ ♦<«r"l>r< N > ♦ *«»*») 
For occurrences (and similarly for holdings), 


tfx^j) ♦ d(xj^3) - n <*- a^jClKN): Vl"«l A Ml'-** A *M2"*2 A Mj'"*3 

An-| Ml | + lM 2 |-7(NXlMill+lM2ll) 
~ 3 M «n(N>. V-X! A M # -x 3 A n - Ijil - tKN)^ 
«•* d(xi^3)-n 

Thus, a(xj, x 2 ) + ^ X3) - a(xj, X3). It follow* that, 

A(f 1. fl) ♦ A(f» fa) " ^lMNJ + ^.Xg) - Atft.ft) ° 

Theorem 5.1& If T-<H.O,C> is a simulation of the synchronous event graph Z, then, 

V^'cH * AzfeV)-kb ^ 

.If r isa path in T connecting two occurrences (holdings), then the time interval 
between V and r* is equal to the number of holdings (occurrences) crossed by #.' 

Proof: (a) Let V - <f }ji|>, 9' - <ty4>, and Z - <N, I>. Thus, 
A^V,**) - (n % -n{i 7(N) + dzfa'l) 
Since 9 is a path from < x to < 2 , the definition of d gives us, 

We know that |e% - ft and, therefore, 

*(>*•> - (nj-n^ y(N) + klg - fQWh 

From Lemma 5J, we have n 2 -ni - Ify The desired result follows immediately. 

(b) Let V - <*ii»i> and »* - <>- Let ji be generated from 9 according to the following 


** < 

> 9 



Which, in turn, products, 

A( V, O - 04-mhKN) ♦ If fc - vCNfefe 
'-Became ot the vaoiiB wfakh m ^ 


w« 1^ fi«o*ibanw» J4 n,-*! - |»|,. Tht 


Theorem 5J6: If <H, O, C> U a HtmilatioQ of tin iroc oronom event traph Z, then, 
Vfi.fjcO: VA^cti: 


If Occurrences ft and f, IntttaUt (ttrminm) Hokjtnfi % Mid Aj respectively, then tht 
time Interval between fi and f, to t l.i iMi l f i s pf» ta iM^ ) | i ii|t iniiii f « i l t And V 

Proof: Welt prove just Part (a). 

Lot f ! - <«i.n t >, ft . «j,n,>. A} - cf^* and A, - <i»*jk. And lit Z *!sN|Ik Wo know 
that «|**| and § g *M t Now tat « be a path in N from th« oniojue output event of *i to «* 
Let 43 bt the unieut output event of if WefOt, 


A<?M2> - (nj-nj) T(N)+ki«iMl-7(N)|*iMli 
^(Aj.Aj) - (mj-w^ ^(N) + bu 2 « 3 | - ^(NJljWjl! 

We have immediately, ki'iMl - ImI + > - Iftf^l- From Lemma 5J, 
we get, mj - nj + (j^ and m 2 - n 2 + |* 2 li- Thus, 

A(*l..*l) - (nj-H^-ni-I^MN) + ki'iHl - YM^ 

- (»2 _B l) T<N) + ki'iMl - Y(N)|J 1 Mli 

• e, 

• s, 

J" < 

• s 3 

• e. 

The notion of 'simultaneity' is defined in a straightforward way. 

Definition: If q j and f 2 * re either two occurrences or two holdings in a simulation of the 
synchronous event graph Z, then, 

f z is called the simultaneity relation. We say that Instances q | and q t are simultaneous 

Property 5.9: If T is a simulation of the synchronous event graph Z, then rg defines an 
equivalence relation on the holdings and occurrences of T. Furthermore, each 
equivalence class induced by r% contains either exclusively holdings or exclusively 

Definition: In a simulation of the synchronous event graph Z, the equivalence classes induced by 
T£ are called simultaneity classes. A simultaneity class of occurrences is called an 
instant of time, or just a time. A simultaneity class of holdings is called an 
( elementary) interval of time. 

We have the following property from Theorem 5J5. 

^^«^¥^gffi^i*e^^ ■*** 


Property BJ& If two Instances in a 
coincident or concurrent 


then they are either 

We have the fottowtnf property from THaaoim M* 

Property 501: If fl , e^ *» and f 4 are mnwm tea itvotUMnofttkt »fnctir«NM* event graph Z. 

flf J A *I*f 4 A fl'Zft * ft*Z?4 

•if 3 A fTf* A *J*Zf4 * fl'Zfl 
If two instances are 


(predecessors) are 

Propertiet 5J0 and &JI mean that in a VyndtroMoi isfflMhtJon', the stoMritaneity classes form a 
•tries of 'slices', with Instants of time and Intervals o f irn s sW s J i l^t ua g *t*tt is INustrated in 
Figure 5.H The rtmulation dopfcttd to generated f rom nWl n^iauoj waul grant in Figure Si. 

Theorem 5J7: If ^ and e s are instances in a timileuon of the lynehroneoaoreBtgraph Z, then, 

fl*Zfc • MA 

*If ft and ft art l i mulm i i s o i ii, < *m f t and f^ meets** phase.' 

Proof: We give the proof for occurrence!, the proof for holdings being *«m*kr. Let Z - <N, I>, 
and tet ft - <xj. *,> and f, - <x 1( n x >. We have, 

1\ T &1 ~ Az(fi.f|)-0 

.'-•• far*th&® *«o>|. »i>-o 

- 3*tn(N): >-#! A .Ve, A |jt| - T^- ^m^N) 
«•► ^wn(N): >-#! A **-«, AW- (H^+fcfcMN) 

Thus, eirzf 2 implies that there exists a path b s tw es n x, and *, whose length U a multiple 
of t(N). It fellows that » l and x, must be in phase. D 

«>■» »•*„ a~- «-_* * '*it)tiitmofxiii»& - 


In Section ft*, we introduced tht neiioa ef «#^> beJiif tht k^ oawrrtnce of «| preceding 
(following) <#,/*,>. For a spchreMm rtuatortM, time to a iww p ta f e rrouh rata** k and the 
time interval between ^j^> and <v»i» 1* ***"* ff" "* ** MM V * VUatMM>t te ■ 
directed graph. 

Definition: If v» and v. are verttoai in the Ui oi fcjj u a nmrt a J dtrfgtod graph O. then, 
d^vj.vj) - mln{W«n<0) | >*iV*ri 
d^^i.ti) li Dii (|ii|ili limiiii) UmiHH fiaw *i * V 

Theorem 5J& If ^p and « > n,> are occttmnra* hi a rtmtttarton of die lynchronoui event 
graph Z~eN,I>, then, 

<«|jn 1 > to the kta eccunwx ef #| preceding <VV 

<#ya«> to the k 01 oscenenei of #| renewing •*|J*|> ■*' 


Proof: From Theorem 5.4 we know that there exit* % path # in the *mukUon from <«iJ»i> to 
<*&,> such that 1^*4 lit be a ndnhnal tongth path m N from #, to #* That to, 
\*Wft*l*& fc^uio*tro»Tlntoni*W 
trom i|Oi|> i nererore, 

•zW-WrWl-M 0) 

Theorem 5J1 atop gives us, 

bhr<N)Wi - W-i*n>Wi (2) 

Combining Lines (1) and (2), we have, 

M-<Mh<N)4ta|. . 

But PHtIh »"d ^hd^Vl*' **** ^ 



From Theorem 5.15(a) we have klg - A z (« 1 ^ 1 ><« 2 ^2 > )- The derired reM,lt fo,tow, • D 

In the simulation of Figure 5.2, we see that <U> U the third occurrence of Event 1 preceding <4,3>. 
We have k«3, y(N)«2, and dj^MJ-S. Thus, 

A(<U>,<43>)-(S-l)x2+3 - 7 
This checks with the value of A(<U>.<4,3>) computed earlier in this section. 

The final results of this section have to do with four functions defined earlier in this 
chapter. For general event graphs, these functions depend upon the set of initial conditions, but 
for synchronous event graphs, they are independent of the initial conditions. 

Property 5J2: For a path m in the synchronous event graph Z-<NJ>, 

Property 5i3: If * is an event in the synchronous event graph Z-<S,E JJ>, then, 
* z -<#) - {seS | l^«n(N>. >s A sep A M '-# A ^MnO-M*)} 
+£{<) - {scS | IjidKN): 'n-4 A S€|» A i- M * A IssHInO'M*)} 

Property 5J4: If ti and « 2 are events in the synchronous event graph Z-<N4>, then, 
tgffiltj - (d^^^-KlM^lW ' V(N) 

Before concluding this section, we should perhaps ay a word about the distinction between 
'system time' and 'observer time'. System time is strictly a system-relative concept, and is observer 
independent Observer time, on the other hand, is relative to a particular observer. In the case of 
a clocked system, the two notions of time are, for practical purposes, the same However, in the 


case of an tmctocke* system, the twnotim ef (kne nif eew Mttk r ste robhmce to one another. 
For example, It might be possible for Insianet f j to mim^ Instance ft In system time, and for * t 
to follow ft In observer time, or vke nena* The enlr Ibing we can sty with certainty Is that if 
there is a causal connection leading from ft to ft, then ft mm precede ft in both system time and 
observer time. 



6.1. Information and Control: 

In Chapters 4 and 5, we examined separately the two components of system behavior: 
information and control In this chapter, results from the two areas are brought together to 
produce a technique for predicting and postdating system behavior. 

As we showed in Chapter S, for each system simulation there is a corresponding control 
simulation, and the two are isomorphic Consider a pair of corresponding simulations. Because 
the control structure is an event graph, the control simulation has the regular properties described 
in Chapter 5. Since the system simulation is isomorphic to the control simulation, it too has these 
regular properties. Of course, the system simulation also has certain , irregular , properties, but these 
are describable using the concepts of information flow. 

It is the irregular properties of system simulations that are the focus of this chapter. 
However, in getting our results, we will take advantage of both the properties of information flow 
and the regular properties of event graph simulations. 

6.2. Transactions: 

Suppose that we have a system simulation and a corresponding control simulation. Within 
the control simulation, there is a total ordering among occurrences of the same meeting (Corollary 
S.4). For each such total ordering, there is a corresponding total ordering in the system simulation 


among occurrence of thoie events belonging » uWretosd meeting. These ideas are inustrated in 
Figures 6.1-6.4. In Figures 61 and M, '***# retreat the lrt n sw»J system mt and the inltiattied 
control structure for the Mtfrtptkne example of Season 17. In Figures 63 and 6.4 we give a 
system simulation and the cw tesp en dt ng centre! rtnwterton . We've Indicated In the control 
simulation the occurrences of Meeting {**}, and weNre wdtawd tt She jpWi sniw l atfcm the 
occurrences of Events 5 and 6 N«n the otte tt o M I^Ws p nii i ■ :. l* woo » «i*,twO sets of 
occurrences. TiHt'Wiwe Mia appose 6i Wlenhg^§S^!pn(rJson*^^F ; 
We adopt this tef iiunotegy: 

Definition: If. within a system stmtfeHen, the nth occ urrence eesedated with Meeting m exists 

- •'-" in i mi ii T i in i imifiiii ir»iii I '" um i HUi ii " H ^ 

If or that ilnunaHenV 

^a *m Meve% enreeeweeo*n»e*j»_ 

For die svstem simulati on fat 

Event & n the Qrjt transection at Mw Mw tfBff - 

Event 6 Is the second te an s acrt e n at Mertn i ft*l 
Event 5 is the third transactional ■MoasMnFwWt ■* 

Now suppose that q is either a helling or an occurrenre m a system sfamiletion. Then 
can speak of the n'th transection at Meeting m 'rekttve tee*. 

flffif ,.>£. /• ; . c. ,v \ ' «'i? ;-:. ;,ft..-4 "I- 

Definition: If T Is a system rtmulatton, 
q is an Instance In T, 

i is an event, I 

mUa meeting. ^ 

it Is a noniero integer, 

































a .* 

2 •. 


1 •, 

g • 

Figure 6.3 A System Simulation 


Figure 6.4 corresponding control Siattilation 


For n<o, the nth occurrence mode** with Mootinrm precedm* o exists and it an 
occurrence of Evint «. \ 

For nxj, the nth occurrence associate! with Meeting ro foBwUny « exists and to an 
^ o mni u m* of Event*. ! '; Tl , : 

In the simulation of Figure 6J, If we kt f be the first (and only) occurrence of Event 4 as 
indicated, then the transactions relative to f are as firm to TeWe*J. Note that for n£-S and for 
n£S, there are no nth transections relative to f Note else that because an occurrence is considered 
both to precede itself and to follow use* <see definition in Section fc& Event 4 is both the last 
transaction and the next transaction at Meeting {M} refcttvt to q. Although thit may not 
correspond to ordinary usage, it dots make the mafliotjnhi tuiailH. 

Meetings m {M} {W} {73J 

Second-to-hut Transactions <o-3) 


1 '■*, r 




Last Transactions (n-1) 





Next Transactions (n«l) 

> ; 

•4 '. . 

v 6 


Second Transections (n«2) 

none ... 




TaMe&l Tra nsactio n! Retfctjee so q 

Having introduced the notion of an event being the n't* transaction at some meeting relative 
to some instance, we can now define the *£of nth titnsactiem relative to en instance. 

Definition: If T Is a system simulation, 
q Is an Instance In T, 
nit a 


t.(f.T) - {««£ | Within T. * Is the nth transection at U^ relative to f] 

*>■*'"*. . - ■***=*» - « "Vt" "" ■ 


If we let T be Hit sfenotatton t« Figaro 6 J and f bt a* dtflned above, then we have the following 
values for t^f/T). 

Lg(f.T) - PJJ 

eY for o&* and for *£& 
The values of tJf.T) an the things about which we're 'going to do our predicting and 



D<9> MHIIBIBH WiiHlW«m» 

The problem* of predicting and postcllcting system behavior are greatly *n*4tf led If the 
system simulations under co nsi deration are 'extendible'. 

,; ? <iti 

Definition: A 

system tkmOukm T is said to be forwards leewards) ntmdlbw iff for each 
tance f in T and each positive integer k tiNreexb* a teowid syewm stawtetton T 


(b) for l£n£k (-kSB£-l) and VmeE*: 

!.(• '.TOnm * O 
T" hat an nth transaction relative to f' for every meeting.' 

(c) t„(e.T) c t.(e'.T'> 

The set of nth transaction! in T relative to 9 is contained within the set 
of nth transections « T' relative to .«'.'. 


Ex t ondlb ttl ty wiss n oad sto the sa si n ai oT'doidloekVla m a Hill lH ii i ap e mi net 

We am Hate a necessary condition and seine toff kssnt oandttiam for extepdibiltty. f torn 
writer work (4l we know that in an event graph, no s v sn t con tami d in a Math circuit can ever 
occur. Therefore; if any ivstem skmrtatlen to to be eatendeW* either forward! ^backwards, the 
initialized control structure mutt be fret of Mank cfeeeJts. SssepOtt thet«his U the case. Then the 
only way for the system net to tang no' in the forwarts ^ifcet J il i ) diwctton as for there to be a 
pattern of holdings on the input (outpo»Hna»ef H ie s a m Mii g each that no event in the meeting 
is forwards (backwards) enabled by those hohtop. A> an example of a backwards liang up', 
consider the simulation in Figure IJ.kln systeai stautatten for the half adder of Figure 115 
with States A and f as initial conditions, Becaim die holdings of A and f do iiot backwards enable 
any event in Meeting {SAW, the rtmetetion Is not backwards extendible. The following are 
sufficient conditions for an* system ilnwott l en i to bo forwards oEtondjbi 

(a) Z* hai no blank drcuitt. 

(b) VmeE*: If a set A consists of exactly one state from each each input Hnk of m, 

tlMt affRt 4t*A 

The following are sufficient conditions for aH systsnf stei«**8n* v»be be«kwaids«xtcndible. 

(a) Z* has no blank circuits. 

(c) Vme£*: If a set A consists of exactly one state from each output link of m, then 

3tem:f*«A *■ '*■'■■'' 

Except for the situation noted above, the tnttiaHmd systsms in Sections 17 aH satisfy these 

i 1 
i i 

11 • • 13 

k . b 
Figure 6.5 A Seaalattea that U Not Backwards Extend** 

Metre proceeding, a word about the phine we n o n a* ' dsadkx * ' is m eider. In the past, 
deadlock in a Petri net has been used to raprwrt thei nwtosn e nding notion Jn an actual system. 
This approach to net sotted to die theory pimni e d hew. If w toterpret occurrences of events as 
r e pr es entin g the ps s w gt of time u described mrM*tm U>lfaM 9 lll& M.p%qpfQi.1lt *w M 
eamspend to tome standl% stiff. Since thti k,«^lnnn^^|n||HM^ i» a reasonable 
aewmptton. Butttweuwtton artoe* M to hew the ph ea oimnw of deadlock is to be represented. 
Sines deadlock Is a VnedV of behavior, there adit pr eh a|rtt3 ho# made (a* defined formally) 

e^^^u I ejfejtt^ej^B^RdBTanunc anp ^kk&t ■ ae^nejptweejpv^v 'e^une^^emonee'e* 

8.4. Prediction Qraohs and PostdicUon Graphs: 

Our efforts in this chapter are concerned with the fottowing problem. 

We know that f tt en imtaiim m seiaeeyea^^^^ with the 

alternative dass c. If we aho knew which chwosnt in e f was an instance of . what would this 
additional knowtedge tell us about the possible pattern* of transactions prior to e and 
subsequent to q ? 


That additional knowledge allows us to kientif y an aUnpH tram among to alternatives. But this 
is exactly the aunt thing that our notion of Wtm mMmmt dees. So the Inf ormetion content' 
of the additional knowledge to ffUvaUnt to the iaf ap mi o n conta* of IN ttonwit htonttfwd. 
Anything that can be deduced from one can be sii a wd from the other. 

Our approach to the problem ts to th«rmctertat al the ways in which the information 
associated with f couM have gotten than (paihhrtiaaj and at tho ways in whkh it could have 
emanated from there (prediction). mformstton conbjnt canshto of a set of excluded modes. 
Because information is 'additive', we can treat each mode In the Information content of q 
separately and then merge the mult. AmMtoMd wtth mfr ii i o amaj a , theraan two suomtu of the 
simulation containing f Om setjuet tram* Hn mmihii mm mepeavand dm other treses IMnto 
the future. Then two mama duwmmi aw i mi hammas of thoiraaaaetten* prior to f and 
fUDseo^iem w g. ■ m 'gonerus/ wwro^nr awwr*ena| wmh ^pp*ie*wewpin* ^jp^m^p^w .^ew^w* w« i " ■• 

In fact, some or the partial mamrmt'may'heouemnlliifam^ oase.jO^oipnejp »w 

an mrtntte nutnoeror ojtsuncf parmn-nmrnfmspeemna moewmw«wjwa!wwaw«s*vw;»e^pijjpfl*»"» 

there is a f tithe way of cheradorimftg ** a* of hectare** *nd fermard* parted binaries, The 

cones described in Section U can be umd to 'sm* up' tha sabaam llayaowsraSr ibepartiatlUsjories. 

This produces a finite sat of litotory •egmentt' as shown in Figure**. This approach is especially 

advantageous since the n*th transaction* relative to f are de t wmln s d by the occurrences in dm nth 

history segment relative to f (aw Corollary &ft "Postdkoen traph» T and 'prodktion graphs' reflect 

the different ways hi which history sagmahu may be < 

" : In ordeF tfr caneafe^ 
are roojuirou. 


'History Segment < 

A 'Back Cone ' 

An Exclusion 

A Front Cone 

Figure 6.6 Subnets Associated with Excluded Mode 


Definition: In a directed graph, a chain U a sequence of am tuch that each arc in the sequence 
has one endpolnt In common with Its prede c ess or and its other endpotnt hi common 
with its successor. (The difference b o t we w a path and a chain to that a path most 
traverse an arc only in the forwards direction, wbtti a chain may traverse an arc in 
either direction.) The sot of chains of the d a «M graph C is denoted C(C). 

Definition: If c U a chain in a directed graph and xyt U a «it*eeuence of c, then thU subtequence 
counts m a forwards (backwards) crossing, of v 
(y to x) and an ait loading from y te x (H» yi 

counts as a forwards <to&95& marine of 7 * **• * ■» *■* taadta f f rain * to * 

Dtf initton: If c to a chain in the directed graph Q and A*a sit of vertices in O. then 

Hd A is the number of forwards crossing* in e of an elsment A mmus the number of 
backwards CTowin|i Wc of an dwasnfm A. 

Definition: For weE* and Mcffl. 

»-(mX) - {tcE | ipoC(rf): *c - f A c'eja A X.nXsj- p A Mupgriiu) 20} (a) 

Tor each event * in 9'(nMl there eajsts a chain e from t to an event in n such that c 
does not intersect the mode M and tht mnnbtr of forwards crossing of states in 
Ud>2*W by e to gretitr than or equal to dn) nonsW of backwards crossings.' 

rVM) - {«c£ | 3c«C(N): *ew A c'-f A V*^ A Id up^w)* 0} (b) 

Tor each event t in 9*{m#tk there exists a chain t form an event in n to t such that c 
does not intersect the mode M and the numbef of forwards croastngs of states in 
UeV^st) by c is greater than or equal «»«he nanoW of back wards crosetngs.' 

v'(m,M) is the set of events that can be contained in a backwards history segment for Meeting m 
and Mode M. v'tm.M) is the set of events that can be contained in a forwards history segment for 
Meeting m and Mode M. 

' d>z*~(*> to the set of links in the back cone of Meeting ta. 1%»"(m) to the set of states belonging 
to those links. 


The requirements given in tht following &nmm*to1mM*mWGI^** l &bl&* 
the system net that correspond to the history i 

Definition: For a subnet R of the system net, a meeting m, and a mode M, we define the foHowing 
requirementi, j. ' 

(la) + »-(»OI) 
(lb) d> c E R c *"W*) 
(2) VoeE*: bnEpJSl 

r contatot no more than; one event ffoat^eacjiHnneilujg.^ 
(S) S R - (Tp^WMtj)' 

•A state it contained in R if f it to ad Jeemt to an event in t and to not OBntained 
tot the mode M.' 


*Sbo am of It cenjtot of thqwarato iH^con^e^eineiitoinR.* 

•Within R. each itattin (S^-Ua^*)) hat ew^ om injnit event and 
one output event' 

<8b) Vs^-Ud^^dn)): Ci)i-(i*)i 

•wnhto R, eaitmaai in (Sjt-U+glmfthas eaaO^one input event and one 
output event' 

the functtom contained m the next deruttnen oerrelpend «• tae front and back boundaries of a 
history segment. 


Definition: For QcjE, mcE*. and Mcffl. 

b-(Q,m,M) - 'Q n (U^ z *-(m» fl (S-%) 
r(am,M) - Q # n (t%*"(nt)) H <S-S M ) 
b^aw,M) - *Q n (l%*-tm)) n (S-S M > 
f ^Om,M) - Q* n (U* z *-»(m)) n (S-S M ) 

We're now ready for postdiction graphs and prediction graphs. 

Definition: The postdiction graph £or Meeting m and Mode m U the graph <tt"(m,M)^'(m,M)> 

u'(m,M) - {£ R | RcjN and R satisfies Requirements la&3,4 and 5a with respect to w and M} 
nf(m,M) - {<A,B>e(u"(m t M)J 2 1 r(AjnMW&*M)*+} 

Definition: The prediction graph for Meeting m and Mode M U the graph <tt 4 (w,M)^ ,, <m,M)> 

tt"*(m,M) - {£ R | RsN and R satisfies Requirements lb.2,3,4, and 5b with respect to m and M) 
w«tm,M) - {<A,B>e<tt1m.M)£ I f -tA^MJ-b^B^M)^} 

To help clarify these ideas, well work through an example Of the three systems considered 
above, the circulating bit pipeline is the most interesting from the standpoint of prediction and 
postdiction. We've redrawn its initialized system net and its initialized control structure in Figure 
6.7. (The parts and modes are shown in Figure 3.14.) Let's consider the meeting {5,6}. For m-{5,6}, 
we have, 

d.-(m)-{{a}.{d},{h,iMk.l}} and Uf <m)«{a4,h4,k,1} 

4^m)-{{b,c},{e/},{g}.{j}} and U**(«Mb,cei,g.j} 

■ ■ tv" • ■. • *.. .-.."■»«"' ..-* ; : 









f' -I 

.. ft- 

»*i-;« ,*t 


















Now suppose that M is the mode associated with £vants 2.4J& and ft. Then there are two subnets 
of the system net satisfying R oo^omonu bOM andla (shewn inUgure 6J(a)) and two subnets 
satisfying Requirement! m&M, and 8b (fthewn In Agwt «J$g| The resulting postdktfon and 
prediction graphs are shewn in Figure** <W« use the same graph i ca l l e piientaUo n as for stale 

Our 4ask now is to shew how predta^ graphs Jftd poetd|ction graphs can be used to 
predict and postdict the patterns of traosaettoru m \$mm m a uHH e n relative to some instance. 
Of course, we can't say anything about how far tf* syseun stmufetien extends, either forwards or 
backwards, but we can say that the pettenw of w e n i aiMwt i must be 'consistent* with certain 

Definition: ForQcjE, 

Qtose££onJ||g!t iff ^4^*1^ *-&% 

'A set of events is selNnnsisteiit iff it cantata* no more than one event from each 

Definition: If ^ and Qj are letf-cocwBttnt sets of «veatt,then, -, 

QlwQs «* «<i«Q|: ¥«|0% «t*#i*«i«*i 

We say that £j and Q| am^gtjeftl with one anomitiff Oj^Qj. 

Two sets of events are cemtoteat with one soother ifV together they contain no more 
than one event f rim each jiiesU n g. ' 

Property fcfc If T is a lyitent sirmilanpn, f is an iirtan* m T, en** to a nonaoro integer, then, 

And, from Req uire me n t (SB, we have the following. 


(a) Backwards 'History Segments' (b) Forwards 'History Segments 

Figure 6.8 

{>^)6 OW 

• 5 >Q OW {'.w}Q b 

{IA7)0 b{ 3 } 

(a) Postdiction Graph 
for Meeting {5,6} 
and Mode {2,4,6,8} 

(b) Prediction Graph 
for Meeting {5,6} 
and Mode {2,4,6,8} 

Figure 6.9 


Property 6.2: V*t £•: VMiHl 

VQ#u"(w,M): QUsttf-corolstam 
VQ#u"*(w,M): Qu self -consistent 
•Each set of events associated with a node la a patfdfetsen (prediction* graph is self - 

The next four theorems comprise our results en prodlcthm and p ost dk t s on. Unfortunately, they 
are quite cu m bersome. They should be repided at only first t o man m stops |n the area of 

Theorem 6J: (a) If T is a backwtrds-txtendlbte system itm u ssrt o n, f is an occurr en c e in T, w-W*. 
and McM), then 3Q*sf<*J4): 

*«<* A tfd,T)*Q 

and there exists a backwards ex ia ndibh system dmuhHon T' with an oauir en co f ' 
such that, 

VneX: ^(fJ^Cf'.TO 
VaeX*: t.,d',T')ne * s) 
Q-»-(i*M)nt 4 d'.T') 

(b) If T U a forwardVextsndible system cfenoltfont f is an occurrence In T, m-Wl^, 
and MeJW, then aQesfWl): 

feQ A «4(f,T)'«Q 

and there exists a forward s -e x tan d i b to system skmibtten T' with an occurrence f ' 
such that, 

&' m& 

Vncl+: t.d.'Ds^d'.TO 
VeeE*: t^e'.T'Kte 4 


Proof: We prove just Part (a). 

Because T is backwards extendible, there exists a system simulation T' with an occurrence 
g' such that, 

VneZ": t n ( ? ,T) S t n ( ? ',T') 
VaeE*: t_|(f '.TOfla + + 

Now since T is backwards extendible, it must be possible to select T' so that it too is 
backwards extendible. Let R be the subnet of N defined as follows. 

E R - xf(m f M)nt_,(? / ,T') 

s R -CE R uE* R )n<s-s M ) 

F R - FfKS R xE R UE R xS R ) 

We can deduce the following about R: 

(a) 4cE R c»-(m.M) f eE R and def. of E R 

(b) VaeE*: |anE R |£l ERS-ity'T') 

(c)S R -CE R UE' R )n(S-S M ) def.ofS R 

(d) F R -FfXS R xE R UE R xS R ) def. of F R 

(e) Vs€(S R -UeS z ^'(w)): fife-d V 4 def. of R and Cor. 4.1 

In other words, R satisfies Requirements la£5,4, and 5a. Thus E R eu"(m,M). We know that 
n is an element of both »"(m,M) and t_j(f',T"). and therefore, teE R . Finally, because 
t-i(?.T) and E R are both subsets of t^'.T'), it follows that t.|(f,T) * E R . □ 

Theorem 6.2: (a) If T is a backwards-extendible system simulation, A is a holding in T, Mcltf), 
and m is the unique input meeting of Kl^, then 3Q€a"(m,M): 

JeXQnm)* A qfoT) » Q 

and there exists a backwards-extendible system simulation T' with a holding h' such 


VneZ": f„(AT) S f„<A'.T') 
Vc€E*: r.^h'.T) n a + 
Q-»-(m,M)nr. 1 (h / ,T / ) . 



(b) If T to » fonwdt- qtttaatbh system e friul s Hsn , A t» » l ie hli n t in T» bUtt&aad w 
is the unlonc output nmiiif e* *e%t* tJuwuBiH^PMefc 

MQf)m)*t A ik,T)«Q. 

and there exists a f orwd»-«ttndJWt sea** HmmnUw T' wJth a hnUtng A' wch 
that v, •--'"■-•■■■ ^ "■-■? 


Q.»tWd)rw +l <h',T') 

Proof: We prove Just Part (a). 

Because T is backwards extendible, there mi^4tWfffKf^lll^fl^^%^ 9 fi^ fMN N ^ n ( * 
such that, 

r-i 0) 

V*€T: l.<A',T') C» 

VecE*: l.|(4'.TO f># <•# T W 

Now since T is backward* exteneibtt, it MUt b«feiettll *#*ete?PP* at that it too is 
backward* extartdtble Let j be %bi.ipttiy, iipig ■ of a" in T'. Be Line <ft f exim. 

"Wei " " " '""" " *"" x *"""- "** 

b*rt*-m«,irt$^m*\}\Kimm *m in In* iwiwxwii m m the 
pro* ofTW*ntXwei*3QeV*^ > 4 * c * ««x* <o ,.~ --« 

*«Q and Q-e*<»ad)ni. t <f,T') 
Because ft (Qnm) end ?•£ 

fc<Qn«r / (4) 

Because f initiates A', 

It follows that, 

Q-e-(w,ld)ni. 1 (A'J') , <5) 

And f inaHy, because f „|(e,T) and Q are both subeits of iffitt <X 

*„1<A.T)-Q <e) 


Lines 1-6 comprise the desired result 

Definition: Within the context of a prediction or postdictton graph <«,»>, we write AVB to mean 
<A, B>€iv. For Aeu, 

V A - {B|BVA} 
A V - {B|AVB} 

Theorem 63 (a) If T is a system simulation, q is an occurrence in T, m - [8) u . Mcl($), QeuimM). 
A is a negative integer, and there exists a backwards-extendible system simulation T' 
with an occurrence q' such that, 

VneZ": t n {q,T)st n iq',T') 
VaeE*: f k <?',T') n a * t> 
Q-»-(m,M)nr k ( ? / ,T') 

then for 7 Q + +, 3Ue v Cfc 

t kA (q.T) " U 

and there exists a backwards-extendible system simulation T" with an occurrence q" 
such that 

9" m &' 

VncZ": r n ( ? ',T') s <„<* ",T") 

VacE*: t kA {q"J") n a * * 

U - i;-(m,M)nr k . 1 ( ? ".T") 

(b) If T is a system simulation, q is an occurrence in T, m-W^, M€l(?X Qeu"*{m,M), * 
is a positive integer, and there exists a forwards-extendible system simulation T' with 
an occurrence q / such that 

VneZ*: ^.Ds^'J') 
Vo€E*: ( k (?',T')na^ 
Q-»VM)nr k ( ? ',T') 

^,.^y:^m^0^^^^0^»^^^^'Hif^ * - - . **. : 

then f or Q v * 

<*.3UoQ v : 

< k *l<*.T)*U 


■ igfupnii 

V»€l* « B (|'.T')C<.«|".T") 
VacE* Vl<f"' T "> n « *■♦ 

u - rtMf>n%4d".T") 

Proof: We prove Part (a). 

Because T' It backwards wrtendlbh, theft oUttt a ape* limulattoo T" with an 
occurrence f" such that, ? * 

*"-?' «-,: ■■■ t ; .•■■ 

VnaT: * B (a ',T') C *,£ ",T") 
¥«€£♦: l k .,(f".T") a d 

Because T' is backward* extend**, it omit be paatfbti la ejfta* T" so that It too is 
backwards extend**. Asmme that tfcfeT} •$ «aft : % #dj^lei'lft»e1» nhmot of N 
defined atfottawj. 

E R .»>Mrf)nr k _ I <f'',T'') 
s R a <' E sl UE l') n ^ s M> 

** - rn^iW*!) 

Now because < k (f 'J") £ ffcCi ",T") and e«B sett caaialft M«*e« from each meeting. 

/ k <j'T'> - t k (f ''T'') 

Weftowhav*. .•■... ..*.., %. , 

q - »-<iajK) n r k <*".T") 
E R - anhM ) n »,.!(•" .to 

It is a straightforward matter to show that, 

ns R .*M)-»-<aiia*) 


Since V Q + <t>, it follows that b-(Q,mM) * ♦ and E R * +. Using the arguments in the 
proof of Theorem 6.1, we then have, 

E R e u"(m,M) 

Thus, E R e v a 

It remains to be shown that t kA {q,T) * E R . This follows from the fact that f k _i(?.T) and 
E R are both subsets of < k _i<?",T"). D 

Theorem 6.4: (a) If T is a system simulation, A is a holding in T, m is the unique input meeting of 
K3*. Meltf). Qett"(m,M), * is a negative integer, and there exists a backwards- 
extendible system simulation T' with a holding A' such that, 

VneT: * B <A,T) S * B (A',T') 
VaeE*: < k (A',T') o K 4 
Q - v'imM) f k (A'.T') 

then for V Q * *, B U e 7 Ct 

* k _l<?.T)*U 

and there exists a backwards-extendible system simulation T" with a holding A" 
such that, 

Vn€F: r n (A'.T')£<„<A".T") 
VacE*: f k .,(A".T") n • * * 

u-»-(m,M)nr k . 1 (A // ,T' / ) 

(b) If T is a system simulation, A is a holding in T, m is the unique output meeting of 
rjfl^, M€l(J), Qett*(m,M) A is a positive integer, and there exists a forwards-extendible 
system simulation T' with a holding A' such that, 

VneZ+t I.WDcl.CA'.T') 
VceE*: t k (A',T')na** 
Q - »VM) n f k (A'.T') 

then for Q v +, 3UtQ 7 : 

and there exists a forwards-extendible system simulation T" with a holding h" such 


VneZ* r > (A'.T')cr 11 (*".T // ) 

Va«E*: * k+1 (A".T") a k 4 

U«»"Wf)ru k ,,(A'',T'') 

Proof: Similar to that of Theorem S3. 

As a limited illustration of the preceding results, consider the system of Figure 6.7 and the 
postdiction graph of Figure 6.9(a). All system simulations are backwards (and forwards) 
extendible. Consider Event 5. It belongs to Meeting {&£}, and its information content contains 
Mode {2,4^,6}. Now if q is any occurrence of Event 5 in a system simulation T, then from 
Theorems 8J(a) and 63(a), we have, 


UfoT) * m 


The odd-numbered transactions preceding q are consistent with {1A5}, while the even numbered- 
transactions preceding f are consistent with {7}. This checks out with the system simulation in 
Figure 6.10. Here we have, 

'. S (?.T)-{4,6,7} 
'-3(?T) - + 


d • • j 

*• c 

Figure 6.10 A System Simulation 



7J. Evaluation: 

With th« theory lntradvocd in the preceding chapters, we tit now able to trait important 
kinds of Petri nets that wem previously eiitslde U«e seeps of any theory. Tht nat rapreaanting the 
half adder it Just one example. From ail indfeiitons, Hie dais of neti contained In our theory Is 
rich and varied. 

The theory has the following advantages: 

(1) The range of concepts expressible within the theory Is extremely broad. Among those 

concepts are soma that are fenttamsntal "Spaee 1 , fens', mtormetion', and 'causaHty* are 
the most notable. 

(2) The theory takes into account the distributed netepe of systems. Concurrency Is the key 

concept here, and concurrency is embedded in thefabric of the theory. - 

(S) Because the theory does not rely on the none* of "total system state*, the complexity of a 
system model Is reduced signlfteamh/. 

(4) Identifying the system net with tht system "hardware', and die set of initial conditions 

with tht system 'software* is a step towards an UHagretsd approach to both hardware 
and software. 

(5) The techniques of die theory lend themselves to automation. 


7.2. Future Work: 

The work that needs to be done falls into two categories: theory and metatheory. The 
metatheory is concerned with four related topics: (1) foundations, (2) semantics, (S) methodology, 
and (4) scope. 

(1) foundations - The theory we've presented depends upon five axioms. We've tried to 

make those axioms plausible, but clearly more work needs to be done. The goal here 
should be to reduce those five axioms to another set of axioms that are more or less 

(2) semantics - A number of concepts have been introduced in the theory, and we need to 

understand the meanings of those concepts. The two that are of the most concern are 
parts and modes. We've said that parts are associated with strictly sequential behavior, 
and that modes are associated with steady-state behavior. But we need to know much 
more about these concepts - in particular, how they relate to concepts already familiar to 
us. (Note that foundations and semantics are intertwined.) 

(S) methodology - For the theory to be a practical tool, there has to be a methodology for 
applying the theory. A set of practical examples is necessary in establishing such a 

(4) scope - The scope of a theory is the range of problems to which it is suited. We must 
find out for which problems the above theory is suited and for which it is not suited. 

In the mathematical development of the theory, there are several areas that deserve attention. 

(1) For a particular system net, there may be several ways of choosing a covering of parts and 

a covering of modes. We need to determine precisely the effects of those choices. We 
already know that the control structure and the information contents of the system 
elements are, in general, affected. 

(2) The four theorems of Chapter 6 are quite cumbersome, and are only the first tentative 

steps in the area of prediction and postdiction. Much more work remains to be done. 
(In this area, Theorem 4.3 ought to play an important role.) 

(3) The ability to predict and postdict system behavior should provide the key to answering 

the following questions about a system. These questions were posed in Section IS. 

Under what conditions will a certain pattern of behavior be produced? 


What arc the consequences of a decision within a system? 

What are the effect* of 1 system modif kation? 

How does behavior m one part of a HWsni lorlWHW liluu tor tn another part? 

How do the outputs of a spurn depend upon the inputs? (Le* What i» the 'function' 
of the system?) 

A systematic technique needs to be de v e lo p ed for each of these outsttons. 

(4) Within this thesis, we have net touched A^en HiobabrtbM. coretderattons. This is a 
major area, and one which witt reejuiro noaiideiihhi effort "EImm ^effort will entail 
relating the approach present e d here with the ideas of Information Theory. In 
partfcuhur, ft wi» be neaiojir j m n**timm*m of Htf— niitluii canter* so Shannon's 

(5) In Section 5* we hitt o du ot d thffinch^^ property 

allowed u» to define instants of ttm* It iwisfo bo fcrtoteabej So invosayate other 
possible constrain* on '-the ""tomm^WmmV^&lmm^ mfr **Mi*J*t space/time 
trameworu nugnt correspono so twei*eutsuoean spaces.; 

The success of these efforts wilt determine the fruttfulness of the ideas presented m this thesis. In 
any eirent, we hope to ha ve stbmtktsd the reader to tthWJ lB | ab o ut the lOMot raised. 



1. Baker, H. G„ Equivalence Problem! of Petri Nets, S.M. Thesis, Department of Electrical 
Engineering, Massachusetts Institute of Technology, June 1973. 

Z Berge, C, Graphs and Hvoergraphs, North-Holland Publishing Co, 1971 

3. Commoner, F. C, Deadlocks in Petri Nets, Report CA-72Q6-2SH, Applied Data Research, Inc. 

Wakefield, Mass, June 1972. 

4. Commoner, F, A. W. Holt, S. Even, and A Pnueli, "Marked Directed Graphs", journal c£ 

Computer and System Sciences. Vol 8, October 1971, pp. 511-523. 

5. Furtek, F. C, Modular Implementation of Petri Neg, S.M. Thesis, Department of Electrical 

Engineering, Massachusetts Institute of Technology, September 1971. 

6. Furtek, F. C "Asynchronous Push-Down Stacks", Computation Structure* Group Memo 86. 

Project MAC, Massachusetts Institute of Technology, August 1973. 

7. Genrich, H. J, Elnfache Nlcht-seauentielle Proiesse (Simple Nonsequential Processes). Bertcht 

Nr. 37, Gesetlschaft fur Mathematik und Datenverarbeitung, Bonn. 1971. 

8. Hack. M. H. T, Analysis of Production Schemata by. Petri Nets, Technical Report M AC-TR-94, 

Project MAC, Massachusetts Institute of Technology, February 197a 

9. Hack, M. H. T, "Extended State-Machine AUocatable Nets", Computation Structures Group 

Memo 78-1, Project MAC, Massachusetts Institute of Technology, June 1974. 

10." Holt, A. W, et at, Final Report gf the Information System Theory Prgjert, Technical Report 
No. RADC-TR-68-305, Rome Air Development Center, Grtffis Air Force Base, New York. 
September 1968. 

1L Holt, A. W. and F. G. Commoner, Events and Conditions. Part I Applied Data Research. Inc. 
New York, 1970. (Chapter I, II and IV appear in Record of the Protect MAC Conference on 
Concurrent Systems and Parallel Computation, ACM, New York, 1970, pp. 9*) 

12. Holt, A. W, Events and Conditions. Part 2. 

13. Holt, A. W„ Events and Conditions. Part 3. (Reprinted in Record of the, Protect MAC 

Conference on Concurrent Systems and Parallel Computation, pp. 33-52.) 

14. Holt, A. W„ "Communication Mechanics", Applied Data Research, Inc. Wakefield. Mass., 1974. 


15. Holt, A. W, "Information at a System RolMrn Concept", Applied Data Research, Inc. 
Wakef ieW, Mast, September 1974. > 

& Jtmtp, J. R, and R,S. ThJefsraJea, X)n the IqolvM ^ of ^ wfrwi o oiw Control Structure*," 
SIAM Journal of Owt|Hiiatian, Vol t Wo^t.>Mit Mfp f*4?. 

17. Paul S. S„ Llmitattcns and CjtnJflJttT 4 ^^ak Jp^ohoji-f^lTot far C oogdAnation 

i &•**> Mono ff7, pTojean* ACTMasimchusettt 


IS. Patrt, C. A^C9mn^rtq t tton.yj^^gjoaa^ RADC-TR-65- 

377, Vok y Rosa* A* linmimmt Cmm.Pimm Ato Jyca Boss^ N«t Yotk 1^6. 
[Originally published in Ohsumi iMHMWJJMJBII isfR jyjMlnl lllirlHun illi IT f i r I ^ 
Westfaltschon btsttaftoi fur ftutwiwinHlli U*m**TWmlM&m*Tffih.HK. 2, 

19. Petri, C A, "Fundamentals of a Theory of Aty i whra n eu j Information Flow", Proceedings of 

~ fHP#MttflN'Mlk^^ 

20. Petri, C. A, "Grundiattttdm sur B o Khreibunf Dbkreter Promat", Colloquium uber 

2L Petri, C. A, Series of talks given at Applied Data Retouch, inc. Wakefield, Mast, August 1971 

22. Petri, C A, "Concepts o f Net pmn?'- H imtto * ^ 

Fou ndati ons of Compunr Sdsnce, ofathemslicel bMtlHai of the Slovak Academy of 
■:- Hie& TtAmJeaatamer WIV 

29. Ramchandaid. C, Anabasi of Awnchronom fifflflfmm Swaum b* Petri Nets. Technical 






alternative 44 
alternative classes 80 
alternativeness relation for Part P 44 

back cone 113 
backwards conflict 97 
backwards conflict dunes 97 
basic circuit 102 
blank circuit 102 
boundary 31 

causal connection 94 
causality relation 90 
chain 156 
circuit 29 
coi n cid en t 91 
concurrent 94 
consistent 160 
control structure SO 

distance 142 

elementary causal connections 91 
elementary circuit 26 
event co m po ne nt 26 
event graph 24 
event-graph de c o m po sa ble 26 
events 24 
extendible 151 

flow relation 24 
follows 94 
forwards conflict 97 
forwards conflict classes 97 
front cone 119 
fundamental circuit 192 

holdings 30 

image 34 
in phase 131 
information content 75 

initial conditions 24 
initiatlud Petri net 24 
initiate 31 
input events 24 

input states 24 
instant of time 199 
interval of time 09 

link 50 

meeting 50 

net 29 
mnsynchronous 129 

occurrences w 
output events 24 
output states 24 

Petri net 24 
phase relation 191 
phase transitions 191 
phases 131 
po stcond itions 24 
precedes 34 
preconditions 24 

self-consistent 160 
simulation 30 
simultaneity classes 139 
simultaneity relation 199 

state component 26 
state graph 24 

state-graph decomposable 26 
starts 24 
strand 35 
subnet 23 

synchronic delay 108 
synchronic distance 125 
synchronous 129 
synchronous system 129 


synchrony property 129 
system 40 
system space 129 

terminate 31 
time 139 

time interval 136 
token loading 102 
transaction 146