Введение
В теории автоматов гибридный автомат (множественное число: гибридные автоматы) — математическая модель для точного описания гибридных систем, например, систем, в которых цифровые вычислительные процессы взаимодействуют с аналоговыми физическими процессами. Гибридный автомат представляет собой машину с конечным числом состояний с конечным набором непрерывных переменных, значения которых описываются системой обыкновенных дифференциальных уравнений. Такая комбинированная спецификация дискретного и непрерывного поведения позволяет моделировать и анализировать динамические системы, состоящие из цифровых и аналоговых компонентов.
Примеры
Простым примером может служить система отопления с комнатным термостатом, где температура в помещении изменяется в соответствии с законами термодинамики и состоянием нагревателя (включен/выключен). Термостат измеряет температуру, выполняет необходимые вычисления и включает или выключает нагреватель. В общем случае, гибридные автоматы применялись для моделирования и анализа широкого спектра встраиваемых систем, включая системы управления транспортными средствами, системы управления воздушным движением, мобильных роботов и биологические процессы.
Связанные модели
Гибридные автоматы представлены несколькими разновидностями: гибридный автомат Алюра–Хензингера является популярной моделью, разработанной главным образом для алгоритмического анализа и проверки моделей гибридных систем. Инструмент проверки моделей HyTech основан на этой модели. Более недавно была разработана модель гибридного автомата ввода-вывода. Эта модель обеспечивает компонентное моделирование и анализ гибридных систем. Другой формализм, полезный для моделирования реализации гибридных автоматов, – это ленивый линейный гибридный автомат.
Решающийся подкласс гибридных автоматов
Учитывая выразительность гибридных автоматов, неудивительно, что простые вопросы достижимости неразрешимы для общих гибридных автоматов. Действительно, прямое сведение задачи о счетчиках к гибридным автоматам с тремя переменными (две переменные для хранения значений счетчика и одна для ограничения расхода единицы времени в каждой локации) доказывает неразрешимость задачи достижимости для гибридных автоматов. Подклассом гибридных автоматов являются автоматы с таймерами, в которых все переменные растут с единой скоростью (то есть все непрерывные переменные имеют производную равную 1). Такие ограниченные переменные могут выступать в качестве переменных-таймеров, называемых часами, и позволяют моделировать системы реального времени. Другие известные разрешимые подклассы включают инициализированные прямоугольные гибридные автоматы, одномерные системы с кусочно-постоянными производными (PCD), автоматы с временной оплатой и многорежимные системы с постоянной скоростью.