In
mathematics and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, 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
consists of
* a set
of events
* a
partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
relation on
called causal dependency,
* an
irreflexive symmetric
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...
relation
called incompatibility (or conflict)
such that
* ''finite causes'': for every event
, the set
of predecessors of
in
is finite
* ''hereditary conflict'': for every events
, if
and
then
.
See also
*
Binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
*
Mathematical structure
In mathematics, a structure is a set endowed with some additional features on the set (e.g. an operation, relation, metric, or topology). Often, the additional features are attached or related to the set, so as to provide it with some additi ...
References
*
Computing terminology
{{math-stub