Например, Бобцов

Сравнительный анализ методов задания ограничений типа at-most-one на примере задачи построения ДКА с использованием программных средств решения SAT

Сборник тезисов
Конференция:VI Всероссийский конгресс молодых ученых
Раздел:Информационные и интеллектуальные системы и технологии
Рубрика:Технологии программирования, искусственный интеллект, биоинформатика
Год:2016

Сравнительный анализ методов задания ограничений типа at-most-one на примере задачи построения ДКА с использованием программных средств решения SAT

УДК:004.832.25

Аннотация

Детерминированные конечные автоматы (ДКА) – это модели, которые распознают регулярные языки. Построение ДКА так или иначе встречается во многих задачах синтаксического распознавания, вычислительной биологии и обработки естественного языка. Для построения автоматов в задачах данного типа успешно применяется подход, основанный на сведении к задаче выполнимости булевой формулы (Boolean satisfiability, SAT). В оригинальной работе ограничения типа at-most-one (не более одной выполненной переменной) на используемые переменные заданы при помощи простейшего биномиального кодирования. Другие же известные работы показывают целесообразность применения иных методов задания ограничений такого же типа. В настоящей работе проводится реализация и сравнение методов задания ограничений at-most-one. Рассматриваются следующие виды кодирования: биномиальное кодирование, двоичное кодирование, кодирование с командиром, кодирование через произведение, последовательное кодирование и двоичное кодирование с командиром.

Материалы конференций