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 ${\displaystyle (E,\leq ,\#)}$ consists of

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

such that

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

See also

• Binary relation
• Mathematical structure

References

• Winskel, Glynn (1987). "Event Structures" (PDF). Advances in Petri Nets. Lecture Notes in Computer Science. Springer.
• event structure in nLab