Доминаторы и пост-доминаторы
Доминирование:
Узел d доминирует узел i (d dom i), если любой возможный путь исполнения от входа до i включает d.
рефлексивность - каждый узел доминирует себя
транзитивность - если a dom b и b dom c, то a dom c
антисимметричность - если a dom b и b dom a, то b = a
Пост-доминирование:
Узел p пост-доминирует узел i (p pdom i), если каждый возможный путь исполнения от i до выхода содержит p. То есть i dom p, если в графе обратить все дуги и поменять вход и выход местами.
Алгоритм поиска доминаторов и пост-доминаторов меня ломает писать
\\dimstar
page revision: 0, last edited: 20 Nov 2006 15:57