Свойства потокового отношения (отношения непосредственного следования). Замыкание отношения непосредственного следования. Свойство сходимости системы.

Моделирование асинхронных процессов

23. Система переходов Келлера: определение, способы задания. Представление асинхронных процессов.

Система переходов Келлера – это двойка <S, F>, где S – нек. конечное мн-во символов, которые будем называть состояниями, а F – бинарное отношение на этом множестве.

Любой кортеж на доменом S будет называться процессом, если отношение порядка в этом кортеже будет согласовано с б.о. непосредственного следования F данной системы переходов.

Т.е. представление пр-ссов в этой метамодели – кортежи состояний

Граф:

Отношение непосредственного следования на множестве состояний системы переходов.

F – бинарное отношение непосредственного следования (частный случай порядка)

– бинарное отношение достижимости (транз. замыкание F)

Свойства б.о. F:

1) Антирефлексивность (если на графе есть петли, то иррефлексивность)

2) Антисимметричность

3) [Транзитивность] (которой может и не быть)

Свойства потокового отношения (отношения непосредственного следования). Замыкание отношения непосредственного следования. Свойство сходимости системы.

Свойства бинарного отношения следования:

1. Антирефлексивность (если на графе появляются петли, то иррефлексивность).

2. Антисимметричность

3. [Транзитивность] – т.е. может быть или не быть

Транзитивное замыкание: .

Транзитивное замыкание является бинарным отношением достижимости.

Помеченная система переходов Келлера: четвёрка объектов < S, F, A, λ >, где S = {s₁, ..., s_n}; F S × S;
A = {α, β, γ, ...}; λ: F → A – функция пометки рёбер (не явл. взаимнооднозн. соответствием, но явл. функцией; разные ребра могут иметь одну метку).

(si sj) Î F si F sj

si →^α sj или si (α) sj

Порождающая система всегда одна, а помеченных систем – сколько угодно.