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.