Длина - формула
Cтраница 2
Основные свойства отображений и выражены в следующих ниже теоремах 6.6, 6.7, 6.8, последние две из которых являются аналогами теорем 3.6 и 3.7 для реализаций термов. Теоремы 6.6, 6.7, 6.8 могут быть доказаны непосредственно индукцией по длине формулы ее. [16]
Основные свойства отображений хй выражены в следующих ниже теоремах 6.6, 6.7, 6.8, последние дое из которых являются аналогами теорем 3.6 и 3.7 для реализаций термов. Теоремы 6.6, 6.7, 6.8 могут быть доказаны непосредственно индукцией по длине формулы а. [17]
 |
Последовательность преобразований для различных трудных задач. [18] |
Число узлов в G, очевидно, меньше длины формулы F, а число ребер не превосходит квадрата числа узлов. Поэтому граф G можно закодировать в виде цепочки, длина которой ограничена полиномом от длины формулы F, и, что еще важнее, такой код можно найти за время, ограниченное полиномом от длины F. Мы покажем, что G содержит g - клику тогда и только тогда, когда формула F выполнима. [19]
Этот метод, если он применен неправильно, может дать в результате экспоненциальное увеличение длины формулы. Здесь мы совместим его применение с недетерминированным алгоритмом таким образом, что кванторы элиминируются по мере перемещения к своим областям действия. [20]
Формулой ( над С, X, , называется функция F: й - C J U, , У которой областью определения ( обозначение Dom ( / 7)) является дерево, такая, что Fr, , если г - внутренняя вершина, и Fr C ] X, если г-концевая вершина. Глубина и длина формулы это соответственно глубина и длина ее области определения. [21]
Транслятор допускает в описании алгоритма на входном языке до 500 операторов каждого типа, 4 000 различных идентификаторов длиной до 78 символов. Списки индексов могут содержать до 21 позиции. Допускается число описаний процедур - до 500, число формальных параметт ров процедуры - до 127, число меток - до 256, длина формулы - до 150 машинных команд. [22]
Страницы: 1 2