Fundamentals of modelling concurrency using discrete relational structures

Abstract.

We consider relational structures $(X,R_1,R_2)$ such that $X$ is a set and $R_1,R_2$ are two binary relations on $X$. For a number of different classes of structures we show that any structure can be represented as the intersection of its maximal extensions. Such a property – called extension completeness – can be seen as a generalisation of Szpilrajn's theorem which states that each partial order is the intersection of its total order extensions. When $R_1$ can be interpreted as causality and $R_2$ as ‘weak’ causality we obtain a model of concurrent histories generalising that based on causal partial orders.