Аннотация:
Рассматриваются предикаты над конечным множеством, которые сохраняет некоторая полурешеточная функция. Такие предикаты названы слабо положительными. Предложено представление таких предикатов в виде особых обобщенных конъюнктивных нормальных форм (ОКНФ). Найдены свойства ОКНФ этих предикатов. На основе полученных свойств предложены более быстрые полиномиальные алгоритмы решения задачи обобщенной выполнимости в случае, когда все исходные предикаты сохраняет некоторая полурешеточная функция.
Ключевые слова:предикат над конечным множеством, функция над конечным множеством, полурешеточная функция, слабо положительный предикат, конъюнктивная нормальная форма, задача обобщенной выполнимости (выполнимости ограничений), полиномиальная задача.
Полный текст:
PDF файл (475 kB)