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

Altальт, альтернативный фрагмент, закрытый фрагмент.

An alt is a fragment with a single initial node.

Let \,A be a set of alts of a cf-graph \,G that contains \,H_1 and \,H_2. \,H_1 is immediately embedded in \,H_2 with respect to \,A if H_1\subset H_2 and there is no alt H_3\in A such that H_1\subset H_3\subset H_2. \,H_1 is called an internal alt with respect to \,A if there is no alt in \,A immediately embedded in \,H, and an external alt with respect to \,A if there is no alt in \,A, into which \,H is immediately embedded.

A set of nontrivial alts \,A is called a nested set of alts (or hierarchy of embedded alts) of the cf-graph \,G if G\in A and, for any pair of alts from \,A, either their intersection is empty or one of them is embedded in the other.

A sequence of cf-graphs G_0, G_1, \ldots, G_r is called a representation of the cf-graph \,G in the form of a nested set of alts \,A (\,A-representation of the cf-graph \,G) if \,G_0=G, \,G_r is a trivial graph and for any \,i>0, \,G_i is a factor cf-graph \,B_i(G), where \,B_i is the set of all external alts with respect to \cup \{A_j: j\in [1,i]\} and \,A_j is the set of all internal alts with respect to A\setminus (\cup \{A_k: k\in [1,i))\}.