name: Методы генерации детерминированных конечных автоматов с использованием сокращения пространства поиска при решении задачи выполнимости
keyword_list: Детерминированный конечный автомат, генерация конечно-автоматных моделей, задача выполнимости, нарушение симметрии, грамматический вывод, уточнение абстракции по контрпримерам
abstract: Целью настоящей диссертации является повышение эффективности точных методов генерации детерминированных конечных автоматов по заданным примерам поведения посредством сокращения пространства поиска при решении задачи выполнимости. По итогам проведенного исследования были получены следующие результаты:
  a)	Предикаты нарушения симметрии, основанные на кодировании алгоритма обхода графа в глубину, которые ранее не предлагались. Новые предикаты нарушения симметрии, основанные на алгоритме обхода графа в ширину, выражающиеся булевой формулой, состоящей из асимптотически меньшего числа дизъюнктов сравнительно с существующим подходом. Помимо этого, впервые предложены предикаты нарушения симметрии, использующие особенности дерева обхода графа в ширину. Предложены точные методы генерации ДКА по заданным примерам поведения, использующие данные предикаты.
  b)	Точный метод генерации ДКА по избыточному набору примеров поведения с использованием сведения к задаче выполнимости и подхода уточнения абстракции по контрпримерам. Точных методов генерации ДКА применимых в случае, когда число примеров поведения излишне велико, ранее не предлагалось.
  c)	Метод генерации всех неизоморфных ДКА минимального размера, удовлетворяющих заданным примерам поведения, с использованием предикатов нарушения симметрии и программных средств решения задачи выполнимости. Ранее не предлагалось методов решения данной задачи.
chairman_dissertation_council.name: Юрий
chairman_dissertation_council.surname: Матвеев
chairman_dissertation_council.patronymic: Николаевич
chairman_dissertation_council.position: профессор (квалификационная категория "профессор-эксперт"), факультет информационных технологий и программирования
chairman_dissertation_council.degree: Доктор технических наук
chairman_dissertation_council.rank: Профессор
chairman_dissertation_council.wos_research_id: d-4188-2014
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Владимир
organization_supervisor.surname: Васильев
organization_supervisor.patronymic: Николаевич
organization_supervisor.position: ректор
organization_supervisor.territory: РОССИЯ
rubrics.code: 28.25.15
rubrics.name: Анализ и синтез конечных автоматов
rubrics.code: 20.01.07
rubrics.name: Теория и методология информатики
oecds.code: 01.02.EX
oecds.name: COMPUTER SCIENCE, THEORY & METHODS
oecds.code: 01.02.ER
oecds.name: COMPUTER SCIENCE, CYBERNETICS
oecds.code: 01.01.PN
oecds.name: MATHEMATICS, APPLIED
speciality_codes.name: Теоретические основы информатики
speciality_codes.code: 05.13.17
supervisors.fio: Ульянцев В.И.
supervisors.scientific_degree: Кандидат технических наук
supervisors.speciality_code: Теоретические основы информатики
supervisors.responsible_type: Научный руководитель
opponents.fio: Уткин Л.В.
opponents.scientific_degree: Доктор технических наук
opponents.speciality_code: Теоретические основы информатики
opponents.responsible_type: Оппонент
opponents.fio: Сандип П.
opponents.scientific_degree: Кандидат технических наук
opponents.speciality_code: Теоретические основы информатики
opponents.responsible_type: Оппонент
protection_organization.short_name: УНИВЕРСИТЕТ ИТМО; НИУ ИТМО; ИТМО
protection_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИТМО"
protection_organization.ogrn: 1027806868154
protection_organization.supervisor_name: ВЛАДИМИР
protection_organization.supervisor_surname: ВАСИЛЬЕВ
protection_organization.supervisor_patronymic: НИКОЛАЕВИЧ
protection_organization.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные автономные учреждения
author_organization.short_name: УНИВЕРСИТЕТ ИТМО; НИУ ИТМО; ИТМО
author_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИТМО"
author_organization.ogrn: 1027806868154
author_organization.supervisor_name: ВЛАДИМИР
author_organization.supervisor_surname: ВАСИЛЬЕВ
author_organization.supervisor_patronymic: НИКОЛАЕВИЧ
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные автономные учреждения