Вычисления на ориентированном графе
Для дальнейшего полезно обобщение изложенных конструкций, предназначенное для описания одновременного вычисления нескольких сложных функций.
Пусть G - связный (но не обязательно ориентированно связный) ориентированный граф без ориентированных циклов. Как и выше, множество вершин G обозначаем v(G), множество ребер - e(G). Пусть, далее, каждой вершине
сопоставлена метка - символ алфавита p( ?), а каждому ребру
сопоставляется метка - конечное множество натуральных чисел P(?', ?) и выполнено условие согласования A: если для данного
множество входящих ребер (?', ?) непусто, то
(является k-местным функциональным символом при некотором k) и семейство множеств
при фиксированном ? образует разбиение множества номеров {1,...,k}.
С помощью транзитивного замыкания G устанавливаем на множестве его вершин v(G) отношения частичного порядка:
, если существует ориентированный путь, ведущий от ?' к ?. Из-за отсутствия ориентированных циклов это отношение антисимметрично: если
и
, то ? совпадает с ?'. Минимальные вершины (к которым не ведет ни одного ребра) называем
входными, а максимальные (от которых не идет ни одного ребра) -
выходными. Обозначим множество входных вершин
, а выходных -
. Метки входных вершин являются символами переменных или констант, метки остальных вершин - функциональные символы.
Определим послойную структуру:
. Нулевой слой состоит из минимальных вершин, первый слой из минимальных вершин графа, получаемого удалением из G нулевого слоя и выходящих из него ребер и т.д. - i+1-й слой состоит из минимальных вершин графа, получаемого удалением из G всех вершин объединения
и содержащих их ребер. Последний слой состоит только из выходных вершин. Предыдущие слои также могут содержать выходные вершины.
С каждой вершиной графа
однозначно связан терм (который мы, следуя традиции предыдущего раздела, также будем обозначать ?). Для его построения удалим из G все вершины, кроме тех, от которых к ? можно пройти по ориентированному пути, а также связанные с ними ребра. Полученный граф обозначим
:
Граф
удовлетворяет условиям теоремы 3, поэтому по нему единственным образом восстанавливается терм (и соответствующая сложная функция).
Пусть задано множество D - область интерпретации и указана интерпретация всех символов, отмечающих вершины графа, а также значения переменных, отвечающих входным вершинам. Тогда по уравнениям функционирования (4) (они полностью сохраняются и для рассматриваемых графов) можно определить значения Z(?) для всех вершин графа. В результате определяются значения всех сложных функций, формулы для которых являются термами, соответствующими вершинам графа G.
Описанные общие графы могут появляться в различных ситуациях. Для дальнейшего важно то, что такие графы возникают, если из графа вычисления сложной функции удалить один или несколько последних слоев.
Содержание раздела
