Сборники тезисов • Информационные и интеллектуальные системы и технологии • Технологии программирования и искусственный интеллект
Сборник тезисов докладов конгресса молодых ученых. Электронное издание. – СПб: Университет ИТМО, 2015.
Разработка предикатов нарушения симметрии на основе поиска в ширину для построения детерминированных конечных автоматов
УДК: 004.832.2
Аннотация:
NP-полная задача построения детерминированного конечного автомата (ДКА) может быть сведена к задаче выполнимости булевой формулы (Boolean satisfiability problem, SAT). Современные методы решения задачи SAT могут эффективно справляться со сложными примерами задачи построения ДКА. В работе представлен подход, позволяющий уменьшить пространство поиска решения задачи SAT при решении поставленной задачи, основанный на нумерации состояний ДКА в порядке обхода в ширину (breadth-first search, BFS). Предложены предикаты нарушения симметрии, которые могут быть добавлены в булевы формулы, представляющие различные задачи построения ДКА. Показано, как применить этот подход для построения ДКА как по точным, так и по зашумленным данным. Основным достоинством предлагаемого подхода является то, что он позволяет точно определять существование искомого ДКА по зашумленным данным.