Programming Research Group Technical Monograph PRG-38

Ludwik Czaja

January/June 1984, 23 + 26 pages, ISBN 0-902928-22-8

Making Nets Abstract and Structured

An abstract net is here taken to be one of the Petri Nets structure but of quite general interpretation: arbitrary objects may be assigned to places and arbitrary transformations on "markings" -- to transitions. Certainly various sorts of Petri Nets may be expressed in this setting, by specifying a particular interpretation. But also such structures as arithmetic or boolean expressions, sequential flowchart schemata, data-flow systems etc. can be represented as abstract nets. The representation however involves pictures -- amorphic collections of lines usually hardly intelligible perhaps apart from simple structures, like trees. But there is a way of structuring large nets from simple easy to understand parts by making use of suitably chosen operators on nets. We chose here a concurrency operator "|" corresponding to that for CSP (vide PRG-22) and in a sense inverse to it -- a subtraction operator "\".

Nets and their Relation to CSP

Starting from a concept of "abstract" net -- an undirected bipartite graph depicting a locality relation rather than flow relation, but interpreted quite generally (transitions represent arbitrary state transformations) -- we define some CSP-like operations on nets. These are: parallel synchronized composition, external choice, asynchronous interleaving, prefix ("first fire transition t then behave like net P") and recursion. They are so defined that the set of firing sequences generated by a composite net equals the respective CSP combination of the sets of firing sequences generated by its components. Thus the underlying model on which the relationship between nets and (a part of) CSP is investigated here is the trace model. The considerations, abstract and semantic at the beginning, become more specific and syntactic as the story proceeds.