Cтраница 4
Уграф G называется одповходовым [21], если каждая его зона имеет единственный вход, или неодновходовым, если в G есть многовходовая зона. Заметим, что не каждая начальная вершина некоторой зоны S уграфа G может быть входом, но если S - это бикомпопента или максимальная многовходовая зона в G, то множества начальных и входных вершин у S совпадают. [46]
Переходя к формальному изложению, обозначим через Е множество тех ребер ( Ь, с) данной сети, для которых 8ь П Dc непусто и отлично от Sb. Пусть входные вершины новой сети находятся во взаимно однозначном соответствии с ее промежуточными вершинами; соединим каждую новую входную вершину с соответствующей промежуточной вершиной. [47]
Пусть / - булева функция п переменных, а ря - соответствующая ей скобочная формула в базисе &, V, П Обозначим через Я ( фп) альтернативную схему, реализующую формулу срп, а через 0 ( Я ( ф)) - граф, соответствующий этой схеме. Граф 0 ( Я ( фп)) имеет п 1 входную вершину, две выходные и N внутренних вершин. На п входных вершин подаются значения входных переменных, и эти вершины связаны с установочными входами альтернативных элементов схемы. На эту входную вершину подается единичный сигнал считывания. [48]
Верхняя и нижняя последовательности пусты. Вычисляем текущий набор А значений предикатных переменных и помещаем его в верхнюю последовательность. Переходим ко входной вершине. [49]
Пусть теперь входной блок схемы среди своих входных потоков имеет как внешние потоки в данную схему, так и ее промежуточные потоки. Примем, что внешний поток выходит из некоторого фиктивного входного блока. Тогда в графе, отвечающем анализируемой схеме, будет введена входная вершина, соответствующая данному фиктивному блоку. Поскольку таким образом введенной входной вершине графа в схеме не отвечает реальный блок, будем называть ее фиктивной входной вершиной. [50]
Материал первой части подсказывает нам, что так сформулированные свойства достижимости и продуктивности хорошо описываются в терминах прямого и обратного транзитивных замыканий: достижимая вершина принадлежит прямому транзитивному замыканию входной вершины графа переходов, а продуктивная вершина принадлежит обратному транзитивному замыканию останова. Важным отличием схем Янова является, однако, что в распознавателях преемники выбираются не произвольно, а предписанным условием способом. Таким образом, недостижимость вершины при построении конфигураций может оказаться замаскированной наличием пути от входной вершины, но содержащего распознаватели с противоречивыми условиями. [51]
Переходя к формальному изложению, обозначим через Е множество тех ребер ( Ь, с) данной сети, для которых 8ь П Dc непусто и отлично от Sb. Пусть входные вершины новой сети находятся во взаимно однозначном соответствии с ее промежуточными вершинами; соединим каждую новую входную вершину с соответствующей промежуточной вершиной. [52]
При малом числе вариантов синтеза орграфов г & к нг к / производят их объединение, а при необходимости вводят в вес той или иной вершины дополнительные проводимости. Однако более типичным является случай с большим числом вариантов синтеза. Поэтому по ранее сформированным коэффициентам Ь ] Л строят различные элементарные графы г - ь и весь орграф e Kj на смешанном графе ГА, приняв в нем одну из вершин в качестве общей ( 0) и введя дополнительную входную вершину и необходимые дуги. Далее можно в этом графе удалить ребра, соединяющие общую вершину 0 и вершину, смежную с входной, если тип ребра ( g или sC) совпадает с типом смежной дуги. При таком преобразовании графа уменьшается число элементов в синтезируемой схеме, но многочлены Ва ( s) и Ла ( s) остаются неизменными, а некоторое уменьшение числа слагаемых в многочлене Л ( s) часто можно компенсировать при параметрическом синтезе. [53]
Пусть / - булева функция п переменных, а ря - соответствующая ей скобочная формула в базисе &, V, П Обозначим через Я ( фп) альтернативную схему, реализующую формулу срп, а через 0 ( Я ( ф)) - граф, соответствующий этой схеме. Граф 0 ( Я ( фп)) имеет п 1 входную вершину, две выходные и N внутренних вершин. На п входных вершин подаются значения входных переменных, и эти вершины связаны с установочными входами альтернативных элементов схемы. На эту входную вершину подается единичный сигнал считывания. [54]
Пусть теперь входной блок схемы среди своих входных потоков имеет как внешние потоки в данную схему, так и ее промежуточные потоки. Примем, что внешний поток выходит из некоторого фиктивного входного блока. Тогда в графе, отвечающем анализируемой схеме, будет введена входная вершина, соответствующая данному фиктивному блоку. Поскольку таким образом введенной входной вершине графа в схеме не отвечает реальный блок, будем называть ее фиктивной входной вершиной. [55]