Определение детерминированных бинарных программ хорошо известно [1]. Эта модель определяется ориентированным ациклическим графом, у которого каждая вершина, за исключением двух выходов, соответствует некоторой переменной и имеет две исходящие дуги, помеченные 0 и 1. Для фиксированных значений переменных вычисление начинается в единственной начальной вершине, идет по дугам в соответствии со значениями переменных и возвращает значение, которым помечен выход. Если на каждом пути каждая переменная встречается не более одного раза, то программа называется один раз читающей (ВРI). Кроме того, если переменные читаются в каком-то определенном порядке, то программа называется упорядоченной ВРI, илиовов.
展开▼
