Inmathematics andcomputer science, anevent structure describes sequences of events that can be triggered by combinations of other events, with certain forbidden combinations of events. Different sources provide more or less flexible mathematical formalizations of the way events can be triggered and which combinations are forbidden.

The most general of these formalizations is given by Glynn Winskel. Winskel formalizes an event structure can be formalized as a triple${\displaystyle (E,\mathcal{C},⊢)}$, in which:

• ${\displaystyle E}$ is a set of events, not necessarily finite.
• ${\displaystyle \mathcal{C}}$ is a family of finite subsets of${\displaystyle E}$, the subsets that are deemed to be consistent (not forbidden). If${\displaystyle C\in \mathcal{C}}$ is one of these consistent sets, then every subset of${\displaystyle C}$ must also be consistent. That is,${\displaystyle \mathcal{C}}$ must be closed under the operation of taking subsets.
• ${\displaystyle ⊢}$ is abinary relation from consistent sets to elements of${\displaystyle E}$. The relation${\displaystyle C⊢e}$, for${\displaystyle C\in \mathcal{C}}$ and${\displaystyle e\in E}$ is interpreted as meaning that when the events so far form set${\displaystyle C}$, thisenables${\displaystyle e}$ to be the next event. When${\displaystyle C⊢e}$, it is required that${\displaystyle C^{\prime }⊢e}$ for every consistent superset${\displaystyle C^{\prime }}$ (with${\displaystyle C\subset C^{\prime }}$ and${\displaystyle C^{\prime }\in \mathcal{C}}$).

According to Winskel's definitions, aconfiguration of an event structure is a subset of${\displaystyle E}$ all of whose finite subsets are consistent and whose events are allsecured. Here, an event is secured when it belongs to a finite sequence of events from the configuration, each of which is enabled by the subset of earlier events from the same sequence.^[1]

Thenlab simplifies these definitions in two ways:

• It replaces the family of consistent events by anirreflexivesymmetric relation${\displaystyle \mathrm{\#}}$ calledincompatibility (orconflict), such that a finite set of events is consistent if and only if it contains no incompatible pair.
• And (either separately or with both simplifications together) it replaces the enabling relation by apartial order relation on${\displaystyle E}$ calledcausal dependency, such that each event has finitely many predecessors, all of which must have happened earlier to enable the event.

For the event structures with both simplifications, which nlab callsprime event structures, the configurations are the downward-closed subsets of the partial order that include no incompatible pairs.^[2]

• Antimatroid, a system of events ordered by enabling subsets but without a consistency requirement

Thismathematics-related article is astub. You can help Wikipedia byexpanding it.

• v
• t
• e

• Causality
• Domain theory
• Mathematics stubs

• All stub articles