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

Ehrenfeucht, A.; Rozenberg, G.

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

MSC:

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

Keywords:

graph grammars; partial orders; partially commutative monoids; dependence graphs; concurrent systems; traces; vector firing sequences

Citations:

Zbl 0624.00017