Критерий полноты для класса планарных предикатных схем

Abstract

В работе исследуется специальный класс дискретных управляющих систем - класс планарных предикатных схем, представляющий собой модификацию модели схем из предикатных элементов, в которой рассматриваются схемы, граф которых является планарным, а входы расположены на внешней грани. По аналогии с моделью СФЭ для полного базиса данной модели формулируется критерий планарной реализуемости; описывается алгоритм преобразования  произвольной непланарной предикатной схемы в заданном базисе в планарную предикатную схему и приводятся оценки сложности "планаризации".