О минимизации инициальных автоматов с таймаутами

Аннотация

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