Interval: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Interval''' --- интервал. An '''interval''' is such an alt <math>I</math> that its initial node belongs to each strongly connected subgraph of <math>I</…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Interval''' --- интервал.  
'''Interval''' --- [[интервал]].  


An '''interval''' is such an alt <math>I</math> that its initial node belongs to each
An '''interval''' is such an alt <math>I</math> that its initial node belongs to each
Строка 20: Строка 20:
A node <math>p</math> is a head of some maximal interval of a cf-graph <math>G</math> if and only if either <math>p</math> is the
A node <math>p</math> is a head of some maximal interval of a cf-graph <math>G</math> if and only if either <math>p</math> is the
initial node of <math>G</math> or <math>p</math> is a terminal node of another maximal interval of <math>G</math>.
initial node of <math>G</math> or <math>p</math> is a terminal node of another maximal interval of <math>G</math>.
[[Категория: Сводимые и регуляризуемые графы]]

Текущая версия от 21:26, 8 октября 2019

Interval --- интервал.

An interval is such an alt [math]\displaystyle{ I }[/math] that its initial node belongs to each strongly connected subgraph of [math]\displaystyle{ I }[/math]. The initial node of interval [math]\displaystyle{ I }[/math] is also called a header node.

An interval [math]\displaystyle{ I }[/math] is maximal if there is no such an interval [math]\displaystyle{ Z }[/math] that [math]\displaystyle{ I }[/math] is a proper subfragment of [math]\displaystyle{ Z }[/math].

For a given control flow graph [math]\displaystyle{ G }[/math] with its initial node [math]\displaystyle{ n_{0} }[/math] and a given node [math]\displaystyle{ n }[/math] of [math]\displaystyle{ G }[/math], the maximal interval with the header [math]\displaystyle{ n }[/math], denoted [math]\displaystyle{ I(n) }[/math], can be constructed by the following three rules: (1) [math]\displaystyle{ n }[/math] is in [math]\displaystyle{ I(n) }[/math]; (2) if all the predecessors of some node [math]\displaystyle{ m \neq n_{0} }[/math] are in [math]\displaystyle{ I(n) }[/math], then [math]\displaystyle{ m }[/math] is in [math]\displaystyle{ I(n) }[/math]; (3) nothing else is in [math]\displaystyle{ I(n) }[/math].

The set of all maximal intervals of a cf-graph [math]\displaystyle{ G }[/math] form a partition of the set of its nodes.

A node [math]\displaystyle{ p }[/math] is a head of some maximal interval of a cf-graph [math]\displaystyle{ G }[/math] if and only if either [math]\displaystyle{ p }[/math] is the initial node of [math]\displaystyle{ G }[/math] or [math]\displaystyle{ p }[/math] is a terminal node of another maximal interval of [math]\displaystyle{ G }[/math].