Сборники тезисов • Информационные и интеллектуальные системы и технологии • Технологии программирования, искусственный интеллект, биоинформатика
Сборник тезисов докладов конгресса молодых ученых. Электронное издание. – СПб: Университет ИТМО, 2017.
Пример заполнения выходных данных:
Закирзянов И.Т., Ульянцев В.И., Шалыто А.А. Сравнительный анализ методов задания ограничений типа at-most-one на примере задачи построения ДКА с использованием программных средств решения SAT // Сборник тезисов докладов конгресса молодых ученых. Электронное издание [Электронный ресурс]. - Режим доступа: ссылка на страницу с тезисом, своб.
Сравнительный анализ методов задания ограничений типа at-most-one на примере задачи построения ДКА с использованием программных средств решения SAT
УДК: 004.832.25
Аннотация:
Детерминированные конечные автоматы (ДКА) – это модели, которые распознают регулярные языки. Построение ДКА так или иначе встречается во многих задачах синтаксического распознавания, вычислительной биологии и обработки естественного языка. Для построения автоматов в задачах данного типа успешно применяется подход, основанный на сведении к задаче выполнимости булевой формулы (Boolean satisfiability, SAT). В оригинальной работе ограничения типа at-most-one (не более одной выполненной переменной) на используемые переменные заданы при помощи простейшего биномиального кодирования. Другие же известные работы показывают целесообразность применения иных методов задания ограничений такого же типа. В настоящей работе проводится реализация и сравнение методов задания ограничений at-most-one. Рассматриваются следующие виды кодирования: биномиальное кодирование, двоичное кодирование, кодирование с командиром, кодирование через произведение, последовательное кодирование и двоичное кодирование с командиром.