Alt: различия между версиями
Glk (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 1: | Строка 1: | ||
'''Alt''' | '''Alt''' — [[альт]], [[альтернативный фрагмент]], [[закрытый фрагмент]]. | ||
An '''alt''' is a ''fragment''with a single ''initial node''. | An '''alt''' is a ''[[fragment]]'' with a single ''[[initial node]]''. | ||
Let <math>A</math> be a set of alts of a ''cf-graph''<math>G</math> that contains <math>H_1</math> and <math>H_2</math>. | Let <math>\,A</math> be a set of alts of a ''[[cf-Graph|cf-graph]]'' <math>\,G</math> that contains <math>\,H_1</math> and <math>\,H_2</math>. | ||
<math>H_1</math> is '''immediately embedded''' in <math>H_2</math> with respect to <math>A</math> if <math>H_1\subset H_2</math> | <math>\,H_1</math> is '''immediately embedded''' in <math>\,H_2</math> with respect to <math>\,A</math> if <math>H_1\subset H_2</math> | ||
and there is no alt <math>H_3\in A</math> such that <math>H_1\subset H_3\subset H_2</math>. | and there is no alt <math>H_3\in A</math> such that <math>H_1\subset H_3\subset H_2</math>. | ||
<math>H_1</math> is called an '''internal''' alt with respect to <math>A</math> if there is no alt in <math>A</math> | <math>\,H_1</math> is called an '''internal''' alt with respect to <math>\,A</math> if there is no alt in <math>\,A</math> | ||
immediately embedded in <math>H</math>, and an '''external''' alt with respect to <math>A</math> | immediately embedded in <math>\,H</math>, and an '''external''' alt with respect to <math>\,A</math> | ||
if there is no alt in <math>A</math>, into which <math>H</math> is immediately embedded. | if there is no alt in <math>\,A</math>, into which <math>\,H</math> is immediately embedded. | ||
A set of nontrivial alts <math>A</math> is called a '''nested set of alts''' (or | A set of nontrivial alts <math>\,A</math> is called a '''nested set of alts''' (or | ||
'''hierarchy of embedded alts''') of the cf-graph <math>G</math> | '''hierarchy of embedded alts''') of the cf-graph <math>\,G</math> | ||
if <math>G\in A</math> and, for any pair of alts from <math>A</math>, either their intersection is empty or | if <math>G\in A</math> and, for any pair of alts from <math>\,A</math>, either their intersection is empty or | ||
one of them is embedded in the other. | one of them is embedded in the other. | ||
A sequence of cf-graphs <math>G_0, G_1, \ldots, G_r</math> is called a representation of | A sequence of cf-graphs <math>G_0, G_1, \ldots, G_r</math> is called a representation of | ||
the cf-graph <math>G</math> in the form of a nested set of alts <math>A</math> ('''<math>A</math>-representation of the cf-graph <math>G</math>''') if <math>G_0=G</math>, <math>G_r</math> is a trivial graph and for any <math>i>0</math>, <math>G_i</math> is | the cf-graph <math>\,G</math> in the form of a nested set of alts <math>\,A</math> ('''<math>\,A</math>-representation of the cf-graph <math>\,G</math>''') if <math>\,G_0=G</math>, <math>\,G_r</math> is a [[trivial graph]] and for any <math>\,i>0</math>, <math>\,G_i</math> is | ||
a factor cf-graph <math>B_i(G)</math>, | a factor cf-graph <math>\,B_i(G)</math>, | ||
where <math>B_i</math> is the set of all external alts with respect to <math>\cup \{A_j: j\in [1,i]\}</math> and | where <math>\,B_i</math> is the set of all external alts with respect to <math>\cup \{A_j: j\in [1,i]\}</math> and | ||
<math>A_j</math> is the set of all internal alts with respect to | <math>\,A_j</math> is the set of all internal alts with respect to | ||
<math>A\setminus (\cup \{A_k: k\in [1,i))\}</math>. | <math>A\setminus (\cup \{A_k: k\in [1,i))\}</math>. | ||
[[Категория: Потоковый анализ программ]] | |||
Текущая версия от 09:02, 9 ноября 2024
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].