Alt

Материал из WEGA
Версия от 17:20, 22 ноября 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

An alt is a fragment with a single initial node.

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

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

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