38. History Preserving Process Graphs

R.J. van Glabbeek (Stanford)

Draft

In this paper I argue that, contrary to what is widely believed, process graphs, or labelled transition systems, have enough structure to model non-interleaved features of concurrency.* To this end I introduce a class of process graphs obeying the restriction that any state not only uniquely characterizes the future of a concurrent behaviour, but also its concurrent history. These history preserving process graphs capture branching time, conjuctive (partial order) causality and disjuctive causality, just like Winskel's event structures, as well as phenonema like resolved conflict that can not be modelled by event structures. They generalize the Scott domains which arise as the duals of general event structures and can be regarded as a step towards a geometric model of concurrency.
KEYWORDS: Concurrency, Process graphs, Event automata, Configuration structures, Event structures, Causality.