Augmented marked graph
Introduction
As a sub-class of Petri nets, augmented marked graphs possess a special structure for modelling systems with shared resources, while exhibiting special properties pertaining to liveness, boundedness, reversibility and conservativeness.
An augmented marked graph is basically a Petri net with a specific set of places called resource places. If removing these resource places and their associated arcs, it will become a marked graph where every cycle is marked. For each resource place, there are pairs of outgoing and incoming transitions connected by elementary paths.
Properties
Some special properties pertaining liveness, boundedness, reversibility and conservativeness of augmented marked graphs are listed below.
- An augmented marked graph is live if and only if it does not contain any potential deadlock. (A potential deadlock is a siphon which would eventually become empty.)
- An augmented marked graph is reversible if it is live.
- An augmented marked graph is live and reversible if and only if every minimal siphon would never become empty.
- An augmented marked graph is live and reversible if every resource place satisfies the R-inclusion property.
- An augmented marked graph is bounded if and only if every place in its R-transform belongs to a cycle.
Application
Augmented marked graphs are often used for modelling systems with shared resources, such as manufacturing systems. Based on the special properties of augmented marked graphs, the properties of the modelled systems, such as liveness, boundedness and reversibility, can be effectively analyzed.
Reference
King Sing Cheung, Augmented Marked Graphs, Springer, 2014. [ISBN. 978-3-319-062427-7]