On the structure of dependence graphs. (English) Zbl 0642.68031

Concurrency and nets. Advances in Petri nets, 141-170 (1987).
[For the entire collection see Zbl 0624.00017.]
The partial orders generated by partially commutative monoids can be represented by the dependence graphs. The partially commutative monoids are widely used as a tool to define the behaviours of concurrent systems, usually under the names: (Mazurkiewicz’s) traces or vector firing sequences. The paper investigates the structure of dependence graphs and in particular it investigates so-called naked dependence graphs, i.e. directed unlabelled graphs obtained from dependence graphs by removing node labels.
Reviewer: R.Janicki


68Q65 Abstract data types; algebraic specification
68R10 Graph theory (including graph drawing) in computer science
68Q45 Formal languages and automata


Zbl 0624.00017