Изменения

Перейти к: навигация, поиск

Согласованный интервал

830 байт добавлено, 3 июнь
Нет описания правки
[[Категория: Параллельное программирование]]
Назовем пару {{Определение|definition='''Интервал''' — упорядоченная пара [[Срез, согласованный срез|срезов]] <tex>[G, H]</tex>такая, что <tex>G \subset le H</tex>, интервалом.<br>}}{{Определение|definition=Интервал $[G, H]$ является '''согласованныйсогласованным''', если <tex>\forall e, g: g \in G \land e \rightarrow g \Rightarrow e \in H</tex>.}}Это значит, что нет сообщений, которые пересекают весь согласованный интервал в обратную сторону (или, что то же самое, нет и "произошло-до" в обратную сторону).Если взять $[G, G]$, то получим в точности определение согласованного среза.
Это значит, что нет сообщений через согласованный Теорема: "интервал в обратную сторону. Отсюда следует$[G, что в согласованном интервале есть H]$ согласован" равносильно "существует согласованный срез. Более того, в обратную сторону тоже верно$X$ внутри интервала: $G \le X \le H$".
В самом делеодну сторону очевидно: если внутри интервала есть согласованный срез, то этот срез в обратную сторону сообщенияпересекать не могут. Значит, не могут они пересекать и весь интервал. В обратную сторону (на экзамене не требуется): рассмотрим произвольный согласованный интервал <tex>[G, H]</tex>.
В доказательстве ниже будем считать, что $a \to a$ для простоты (но можно переписать доказательство и без рефлексивности).
<tex>G</tex> может не быть согласованным срезом (если есть стрелочка из <tex>H \setminus G</tex> в <tex>G</tex>), что печально.
Но можно попробовать пойти по стрелочкам в обратную сторону.
Придумаем формальное "замыкание" <tex>G</tex>: возьмём множество <tex>X = \{ e \mid \exists g \in G \colon e \rightarrow g \}</tex>.
292
правки

Навигация