РОССИЙСКАЯ ФЕДЕРАЦИЯ
ФЕДЕРАЛЬНАЯ СЛУЖБА ПО ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ
ГОСУДАРСТВЕННАЯ РЕГИСТРАЦИЯ ПРОГРАММЫ ДЛЯ ЭВМ

Номер регистрации (свидетельства): 2016660665

Дата регистрации: 20.09.2016

Номер и дата поступления заявки: 2016618241 27.07.2016

Дата публикации: 20.10.2016

Контактные реквизиты:
zakirzyanov@rain.ifmo.ru
	
Авторы:
Закирзянов Илья Тимурович,
Ульянцев Владимир Игоревич,
Шалыто Анатолий Абрамович

Правообладатель:
федеральное государственное автономное образовательное учреждение высшего образования «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики»

Программа для ЭВМ создана по государственному контракту

государственный заказчик: Министерство образования и науки РФ

Название программы для ЭВМ:
Программный комплекс методов машинного обучения DFA-Inductor для построения детерминированных конечных автоматов

Реферат:
Программа предназначена для построения детерминированных конечных автоматов минимального или заданного размера по заданным обучающим словарям. В программе реализовано сведение решаемой задачи к задаче выполнимости булевой формулы (SAT). По входным словарям, заданным в стандартном формате и представляющим примеры работы автомата, который необходимо найти, строится префиксное дерево и граф совместимости. Затем по данным структурам строится булева формула, которая передается на вход стороннему программному средству для решения задачи SAT. В случае, если формула удовлетворима, то по ней восстанавливается искомый автомат в формате DOT. В программе реализованы несколько подходов к нарушению симметрии: подход, основанный на поиске большой клики графа совместимости, известный ранее, и новый подход, основанный на нумерации искомого автомата в порядке его обхода алгоритмами обхода в ширину (BFS) и в глубину (DFS). Также в программе реализован алгоритм проверки на соответствие найденного автомата входным данным.

Тип реализующей ЭВМ: IBM PC-совмест. ПК на базе процессора Intel х86

Язык программирования: Java

Вид и версия операционной системы: GNU/Linux, Windows

Объем программы для ЭВМ: 119 Кб