Event structure

In mathematics and computer science, an event structure represents a set of events, some of which can only be performed after another (there is a dependency between the events) and some of which might not be performed together (there is a conflict between the events).

Formal definition

An event structure [math]\displaystyle{ (E,\leq,\#) }[/math] consists of

• a set [math]\displaystyle{ E }[/math] of events
• a partial order relation on [math]\displaystyle{ E }[/math] called causal dependency,
• an irreflexive symmetric relation [math]\displaystyle{ \# }[/math] called incompatibility (or conflict)

such that

• finite causes: for every event [math]\displaystyle{ e \in E }[/math], the set [math]\displaystyle{ [e] = \{f\in E \mid f\leq e\} }[/math] of predecessors of [math]\displaystyle{ e }[/math] in [math]\displaystyle{ E }[/math] is finite
• hereditary conflict: for every events [math]\displaystyle{ d,e,f \in E }[/math], if [math]\displaystyle{ d \leq e }[/math] and [math]\displaystyle{ d \# f }[/math] then [math]\displaystyle{ e \# f }[/math].

See also

• Binary relation
• Mathematical structure

References

• Winskel, Glynn (1987). "Event Structures". Advances in Petri Nets (Springer). http://www.cl.cam.ac.uk/~gw104/EvStr.pdf. 
• event structure in nLab