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 …