Структура мероприятия

В математике и информатике структура событий описывает последовательности событий, которые могут быть вызваны комбинациями других событий, с определенными запрещенными комбинациями событий. Различные источники предоставляют более или менее гибкие математические формализации того, как события могут быть вызваны, и какие комбинации запрещены.

Наиболее общая из этих формализаций дана Глинном Винскелем. Винскель формализует структуру событий, которая может быть формализована как тройка , в которой: ( Э , С , ⊢ ) {\displaystyle (E,{\mathcal {C}},\vdash )}

  • Э {\displaystyle E} это набор событий, не обязательно конечный.
  • С {\displaystyle {\mathcal {C}}} — это семейство конечных подмножеств , подмножества, которые считаются согласованными (не запрещенными). Если — одно из этих согласованных множеств, то каждое подмножество также должно быть согласованным. То есть, должно быть замкнуто относительно операции взятия подмножеств. Э {\displaystyle E} С ∈ С {\displaystyle C\in {\mathcal {C}}} С {\displaystyle С} С {\displaystyle {\mathcal {C}}}
  • ⊢ {\displaystyle \vdash} является бинарным отношением от согласованных множеств к элементам . Отношение , для и интерпретируется как означающее, что когда события до сих пор образуют множество , это позволяет быть следующим событием. Когда , требуется, чтобы для каждого согласованного надмножества (с и ). Э {\displaystyle E} С ⊢ е {\displaystyle C\vdash e} С ∈ С {\displaystyle C\in {\mathcal {C}}} е ∈ Э {\displaystyle e\in E} С {\displaystyle С} е {\displaystyle е} С ⊢ е {\displaystyle C\vdash e} С ′ ⊢ е {\displaystyle C'\vdash e} С ′ {\displaystyle C'} С ⊂ С ′ {\displaystyle C\subset C'} С ′ ∈ С {\displaystyle C'\in {\mathcal {C}}}

Согласно определениям Винскеля, конфигурация структуры событий представляет собой подмножество всех конечных подмножеств, все события которого согласованы и все события которого защищены . Здесь событие защищено, когда оно принадлежит к конечной последовательности событий из конфигурации, каждое из которых включено подмножеством более ранних событий из той же последовательности. [1] Э {\displaystyle E}

Nlab упрощает эти определения двумя способами :

  • Он заменяет семейство непротиворечивых событий нерефлексивным симметричным отношением , называемым несовместимостью (или конфликтом ), таким образом, что конечный набор событий является непротиворечивым тогда и только тогда, когда он не содержит несовместимых пар. # {\displaystyle \#}
  • И (либо по отдельности, либо с обоими упрощениями вместе) он заменяет разрешающее отношение отношением частичного порядка , называемым причинной зависимостью , таким образом, что каждое событие имеет конечное число предшественников, все из которых должны были произойти ранее, чтобы разрешить событие. Э {\displaystyle E}

Для структур событий с обоими упрощениями, которые nlab называет простыми структурами событий , конфигурации представляют собой замкнутые вниз подмножества частичного порядка, которые не включают несовместимых пар. [2]

Смотрите также

  • Антиматроид , система событий, упорядоченная путем включения подмножеств, но без требования согласованности

Ссылки

  1. ^ Winskel, Glynn (1986), "Структуры событий" (PDF) , в Brauer, Wilfried; Reisig, Wolfgang; Rozenberg, Grzegorz (ред.), Petri Nets: Central Models and Their Properties, Advances in Petri Nets 1986, Часть II, Proceedings of an Advanced Course, Bad Honnef, Германия, 8-19 сентября 1986 г. , Lecture Notes in Computer Science, т. 255, Springer, стр.  325–392 , doi :10.1007/3-540-17906-2_31, ISBN 978-3-540-17906-1
  2. ^ Структура мероприятия в n Lab


Значок заглушки

Эта статья, связанная с математикой, является заглушкой . Вы можете помочь Википедии, расширив ее.

Взято с "https://en.wikipedia.org/w/index.php?title=Event_structure&oldid=1233035557"