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))\}$.