ПОСТРОЕНИЕ ДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ ПО ПРИМЕРАМ ПОВЕДЕНИЯ С ИСПОЛЬЗОВАНИЕМ ПОДХОДА УТОЧНЕНИЯ АБСТРАКЦИИ ПО КОНТРПРИМЕРАМ
Аннотация:
Предмет исследования. Рассмотрена задача построения детерминированного конечного автомата минимального размера по примерам поведения. Разработан и реализован комбинированный метод решения данной задачи на основе сведения к задаче выполнимости булевых формул и с использованием подхода уточнения абстракции по контрпримерам. Метод. Предлагается в качестве исходных данных использовать не все примеры поведения сразу, а начинать с какого-то их подмножества, и строить соответствующий автомат, используя метод на основе сведения к задаче выполнимости. Затем построенный автомат проверяется на соответствие всем остальным примерам поведения. Те примеры, на которых поведение автомата расходится с желаемым, являются контрпримерами. Часть контрпримеров добавляется к исходным примерам поведения и процесс повторяется. Основные результаты. Предложенный метод реализован как часть программного комплекса для решения задачи построения детерминированного конечного автомата по примерам поведения на языке Python. Проведено эксперимен- тальное сравнение разработанного метода с методом, основанным на сведении к задаче выполнимости булевых формул, но без использования подхода уточнения абстракции. Практическая значимость. Экспериментальное исследование показало, что разработанный метод целесообразно использовать при условии, что число приме- ров поведения достаточно велико — хотя бы в двести раз превышает количество состояний автомата, — и, как следствие, строящаяся булева формула содержит десятки и сотни миллионов дизъюнктов.
Ключевые слова:
Постоянный URL
Статьи в номере
- ЭКСПЕРИМЕНТАЛЬНЫЙ МЕТОД ОПРЕДЕЛЕНИЯ НАПРАВЛЕНИЯ УСАДКИ ПРИ ГОЛОГРАФИЧЕСКОЙ ЗАПИСИ В СРЕДЕ BAYFOL HX
- ПОДХОД К ВЕДЕНИЮ АЭРОСЪЕМКИ МЕСТНОСТИ С ИСПОЛЬЗОВАНИЕМ КОМПОНОВКИ ОПТИКО-ЭЛЕКТРОННЫХ КАМЕР
- МЕТОДЫ ОЦЕНКИ КАЧЕСТВА ИЗОБРАЖЕНИЙ БИНАРНЫХ ОБЪЕКТОВ, ВОССТАНОВЛЕННЫХ С ПОМОЩЬЮ СИНТЕЗИРОВАННЫХ ГОЛОГРАММ-ПРОЕКТОРОВ
- ДЕФЕКТОСКОПИЯ БАЛТИЙСКОГО ЯНТАРЯ: ОПТИЧЕСКИЙ АНАЛИЗ МАКРО- И МИКРОСТРУКТУРЫ
- ВОЛОКОННО-ОПТИЧЕСКАЯ ИЗМЕРИТЕЛЬНАЯ СИСТЕМА ДЛЯ ОПРЕДЕЛЕНИЯ ПОЛОЖЕНИЯ И ИЗГИБОВ ПРОТЯЖЕННЫХ ОБЪЕКТОВ В ПРОСТРАНСТВЕ
- ВОССТАНОВЛЕНИЕ ДИСКРЕТНЫХ СПЕКТРОВ, ИЗЛУЧАЕМЫХ ВЕЩЕСТВОМ В ГЛУБОКОМ ВАКУУМЕ, С ПОМОЩЬЮ АЛГОРИТМА ИНТЕГРАЛЬНОЙ АППРОКСИМАЦИИ
- АЛГЕБРАИЧЕСКИЙ МЕТОД ИССЛЕДОВАНИЯ РОБАСТНОСТИ ИНТЕРВАЛЬНЫХ ДИНАМИЧЕСКИХ СИСТЕМ
- ИССЛЕДОВАНИЕ СИСТЕМЫ НАВИГАЦИИ ДЛЯ МОБИЛЬНЫХ РОБОТОВ НА ОСНОВЕ ОДНОВРЕМЕННОЙ ЛОКАЛИЗАЦИИ И ПОСТРОЕНИЯ КАРТЫ
- ОБЗОР МЕТОДОВ ОПРЕДЕЛЕНИЯ РАЗМЕРОВ И МОРФОЛОГИИ ВЕЗИКУЛ НИОСОМАЛЬНОЙ ДИСПЕРСИИ
- МЕТОДЫ ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ В ПРОСТЫХ СЕМАНТИЧЕСКИХ СЕТЯХ
- ДИСТИЛЛЯЦИЯ НЕЙРОСЕТЕВЫХ МОДЕЛЕЙ ДЛЯ ДЕТЕКТИРОВАНИЯ И ОПИСАНИЯ КЛЮЧЕВЫХ ТОЧЕК ИЗОБРАЖЕНИЙ
- МЕТОД ОБЕСПЕЧЕНИЯ ПЕРЕНОСИМОСТИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ НА ОСНОВЕ ПЕРЕНАЦЕЛИВАЕМОЙ СРЕДЫ ВЫПОЛНЕНИЯ ПРОГРАММ
- ДЕТЕКТИРОВАНИЕ И КЛАССИФИКАЦИЯ ДОРОЖНЫХ ЗНАКОВ В РЕАЛЬНОМ ВРЕМЕНИ НА ОСНОВЕ АЛГОРИТМА YOLO ВЕРСИИ 3 (на англ. яз)
- ПРИМЕНЕНИЕ НЕЙРОННОЙ СЕТИ АРХИТЕКТУРЫ U-NET ДЛЯ ЗАДАЧИ ЛОКАЛИЗАЦИИ НАРУШЕНИЙ ЦЕЛОСТНОСТИ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ
- ДЕТЕРМИНИРОВАННЫЕ СИСТЕМЫ С ЕСТЕСТВЕННЫМ КВАНТОВАНИЕМ
- ТЕХНИЧЕСКАЯ ПНЕВМОСИСТЕМА ДЛЯ РАЗРАБОТКИ УСТРОЙСТВ С ОПРЕДЕЛЕННЫМИ ФУНКЦИОНАЛЬНЫМИ ВОЗМОЖНОСТЯМИ
- СТАТИСТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПЕРЕДАТОЧНЫХ ОТНОШЕНИЙ КОЛЕННОГО СУСТАВА
- СРАВНЕНИЕ АЛГОРИТМОВ ФОРМИРОВАНИЯ ДИАГРАММ НАПРАВЛЕННОСТИ МИКРОФОННЫХ РЕШЕТОК В СРЕДЕ MATLAB
- QR-КОДЫ С АНИМАЦИЕЙ ДЛЯ ЦИФРОВЫХ ПРОПУСКОВ
- ВЛИЯНИЕ ФОТОАКТИНИЧНОГО ИЗЛУЧЕНИЯ НА ПОКАЗАТЕЛЬ ПРЕЛОМЛЕНИЯ ОРГАНИЧЕСКИХ СОКРИСТАЛЛОВ НА ОСНОВЕ СОЕДИНЕНИЙ АМИНОПИРИДИНОВОГО РЯДА