Задача анализа свойств состояний
Задача анализа свойств состояний (Data flow analysis problem) - Рассматривается полурешетка свойств [math]\displaystyle{ (L,\sqcap) }[/math], не содержащая бесконечных цепей, множество преобразователей свойств [math]\displaystyle{ F }[/math] и функция [math]\displaystyle{ M }[/math], ставящая в соответствие каждой дуге [math]\displaystyle{ u }[/math] анализируемого уграфа [math]\displaystyle{ G=(V,U) }[/math] функцию эффекта дуги [math]\displaystyle{ M(u)\in F }[/math].
Прямая З.а.с.с формулируется как задача нахождения так называемой полной разметки --- такой функции [math]\displaystyle{ A:V\rightarrow L }[/math], что
[math]\displaystyle{ A(p)=\sqcap\{f_{\alpha} (a_0):\alpha \mbox{ --- путь от начальной вершины до } p\}, }[/math]
где [math]\displaystyle{ a_0 }[/math] --- некоторое свойство, сопоставляемое с начальной вершиной уграфа, а [math]\displaystyle{ f_{\alpha} }[/math] --- функция эффекта пути, полученная композицией функций эффектов составляющих его дуг. Указанная задача алгоритмически неразрешима и допускает эффективное решение лишь для узких своих подклассов таких, как, например, дистрибутивные З.а.с.с., в которых [math]\displaystyle{ F }[/math] состоит только из дистрибутивных функций. Поэтому обычно рассматриваются алгоритмы нахождения приближенных решений задачи, связанных с нахождением корректных разметок --- таких [math]\displaystyle{ B:V\rightarrow L }[/math], что [math]\displaystyle{ B(p)\sqsubseteq f_{\alpha}(a_0) }[/math] для любых вершины [math]\displaystyle{ p }[/math] и пути [math]\displaystyle{ \alpha }[/math] из [math]\displaystyle{ a_0 }[/math] в [math]\displaystyle{ p }[/math].
В отличие от прямой обратная З.а.с.с. предполагает известными начальное свойство для конечной вершины уграфа и обратное направление применения функций эффектов дуг.
В общей постановке с каждой дугой уграфа могут связываться функции ее эффектов как в прямом, так и в обратном направлении.
Другие названия --- Задача потокового анализа и Задача глобального анализа потока данных.
Литература
[Касьянов/88], [Котов-Сабельфельд]
