Interval

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].