Event structure: Difference between revisions

From HandWiki
imported>WikiEd2
linkage
 
Rjetedi (talk | contribs)
0 edits
over-write
 
Line 1: Line 1:
In [[Mathematics|mathematics]] and [[Computer science|computer science]], an '''event structure''' represents a [[Set (mathematics)|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).
In [[Mathematics|mathematics]] and [[Computer science|computer science]], an '''event 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 how events can be triggered and which combinations are forbidden.
==Formal definition==
 
An '''event structure''' <math>(E,\leq,\#)</math> consists of
Glynn Winskel gave the most general of these formalizations. Winskel formalizes an event structure as a triple <math>(E,\mathcal{C},\vdash)</math>, in which:
* a set <math>E</math> of '''events'''
*<math>E</math> is a set of events, not necessarily finite.
* a partial order relation on <math>E</math> called '''causal dependency''',
*<math>\mathcal{C}</math> is a family of finite subsets of <math>E</math>, the subsets that are deemed to be consistent (not forbidden). If <math>C\in\mathcal{C}</math> is one of these consistent sets, then every subset of <math>C</math> must also be consistent. That is, <math>\mathcal{C}</math> must be closed under the operation of taking subsets.
* an irreflexive symmetric relation <math>\#</math> called '''incompatibility''' (or '''conflict''')
*<math>\vdash</math> is a [[Binary relation|binary relation]] from consistent sets to elements of <math>E</math>. The relation <math>C\vdash e</math>, for <math>C\in\mathcal{C}</math> and <math>e\in E</math> is interpreted as meaning that when the events so far form set <math>C</math>, this ''enables'' <math>e</math> to be the next event. When <math>C\vdash e</math>, it is required that <math>C'\vdash e</math> for every consistent superset <math>C'</math> (with <math>C\subset C'</math> and <math>C'\in\mathcal{C}</math>).
such that
According to Winskel's definitions, a ''configuration'' of an event structure is a subset of <math>E</math> all of whose finite subsets are consistent and whose events are all ''secured''. 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.{{r|winskel}}
* ''finite causes'': for every event <math>e \in E</math>, the set <math>[e] = \{f\in E \mid f\leq e\}</math> of predecessors of <math>e</math> in <math>E</math> is finite
 
* ''hereditary conflict'': for every events <math>d,e,f \in E</math>, if <math>d \leq e</math> and <math>d \# f</math> then <math>e \# f</math>.
The nlab simplifies these definitions in two ways:
*It replaces the family of consistent events by an irreflexive symmetric relation <math>\#</math> called ''incompatibility'' (or ''conflict''), 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 a partial order relation on <math>E</math> called ''causal 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 calls ''prime event structures'', the configurations are the downward-closed subsets of the partial order that include no incompatible pairs.{{r|nlab}}


==See also==
==See also==
* [[Binary relation]]
* [[Antimatroid]], a system of events ordered by enabling subsets but without a consistency requirement
* [[Mathematical structure]]


==References==
==References==
* {{cite news | last = Winskel | first = Glynn | url = http://www.cl.cam.ac.uk/~gw104/EvStr.pdf | title = Event Structures | journal = Advances in Petri Nets | publisher = Springer | series = Lecture Notes in Computer Science | year = 1987}}
<references>
* [https://ncatlab.org/nlab/show/event+structure event structure] in nLab
 
[[Category:Computing terminology]]
<ref name=winskel>{{citation
| last = Winskel | first = Glynn
| editor1-last = Brauer | editor1-first = Wilfried
| editor2-last = Reisig | editor2-first = Wolfgang
| editor3-last = Rozenberg | editor3-first = Grzegorz
| contribution = Event structures
| contribution-url = https://www.cl.cam.ac.uk/~gw104/EvStr.pdf
| doi = 10.1007/3-540-17906-2_31
| pages = 325–392
| publisher = Springer
| series = Lecture Notes in Computer Science
| title = Petri Nets: Central Models and Their Properties, Advances in Petri Nets 1986, Part II, Proceedings of an Advanced Course, Bad Honnef, Germany, 8-19 September 1986
| volume = 255
| year = 1986| isbn = 978-3-540-17906-1
}}</ref>
 
<ref name=nlab>{{nlab|id=event+structure|title=Event structure}}</ref>
 
</references>
 
[[Category:Causality]]






{{Sourceattribution|Event structure}}
{{Sourceattribution|Event structure}}

Latest revision as of 06:51, 28 May 2026

In mathematics and computer science, an event 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 how events can be triggered and which combinations are forbidden.

Glynn Winskel gave the most general of these formalizations. Winskel formalizes an event structure as a triple (E,𝒞,⊢), in which:

  • E is a set of events, not necessarily finite.
  • 𝒞 is a family of finite subsets of E, the subsets that are deemed to be consistent (not forbidden). If C∈𝒞 is one of these consistent sets, then every subset of C must also be consistent. That is, 𝒞 must be closed under the operation of taking subsets.
  • ⊢ is a binary relation from consistent sets to elements of E. The relation C⊢e, for C∈𝒞 and e∈E is interpreted as meaning that when the events so far form set C, this enables e to be the next event. When C⊢e, it is required that C′⊢e for every consistent superset C′ (with C⊂C′ and C′∈𝒞).

According to Winskel's definitions, a configuration of an event structure is a subset of E all of whose finite subsets are consistent and whose events are all secured. 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]

The nlab simplifies these definitions in two ways:

  • It replaces the family of consistent events by an irreflexive symmetric relation # called incompatibility (or conflict), 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 a partial order relation on E called causal 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 calls prime event structures, the configurations are the downward-closed subsets of the partial order that include no incompatible pairs.[2]

See also

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

References

  1. ↑ Winskel, Glynn (1986), "Event structures", in Brauer, Wilfried; Reisig, Wolfgang; Rozenberg, Grzegorz, Petri Nets: Central Models and Their Properties, Advances in Petri Nets 1986, Part II, Proceedings of an Advanced Course, Bad Honnef, Germany, 8-19 September 1986, Lecture Notes in Computer Science, 255, Springer, pp. 325–392, doi:10.1007/3-540-17906-2_31, ISBN 978-3-540-17906-1, https://www.cl.cam.ac.uk/~gw104/EvStr.pdf 
  2. ↑ Event structure in nLab




Retrieved from "https://handwiki.org/wiki/index.php?title=Event_structure&oldid=4356682"