Иерархия вложенных альтов

Иерархия вложенных альтов (Hierarchy of nested alts) — множество нетривиальных альтов $A=\{H_i\}$ управляющего графа таких, что для любых двух альтов либо их пересечение пусто, либо один целиком содержится в другом.

Альт $H_i\in A$ непосредственно вложен в альт $H_j\in A$ относительно $A$, если $H_i\subset H_j$ и в $A$ не существует такого альта $H_k$, что $H_i\subset H_k\subset H_j$.

Альт $H_i\in A$ называется внутренним альтом относительно $A$, если в $A$ не существует альтов, непосредственно вложенных в $H_i$ и внешним альтом относительно $A$, если в $A$ не существует альта, в который $H_i$ непосредственно вложен.

Последовательность уграфов $G_0,G_1,\dots ,G_r$ называется представлением уграфа $G$ в виде иерархии вложенных альтов $A$ (A-граф, A-представление уграфа $G$), если

• $G_0=G$,

• $G_r$ — тривиальный уграф и

• для любого $i$ уграф $G_i$ получается из $G_{i-1}$ стягиванием в вершины всех внешних альтов относительно $\bigcup \{A_j:1\le j\le i\}$, где $A_j$ — множество всех внутренних альтов относительно $A\setminus \bigcup \{A_s:1\le s<j\}$.

Литература

• Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.