• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

О сложности верификации автоматов-преобразователей над коммутативными полугруппами

С. 68-71.
Захаров В. А., Гнатенко А. Р.

В статье в качестве формальной модели последовательных реагирующих систем была предложена модель вычислений конечных автоматов-преобразователей, работающих над полугруппами действий. Для спецификации поведений таких автоматов был предложен специальный вариант темпоральной логики линейного времени LTL-FL (LTL with Formal Languages). Формальные языки (множества конечных слов фиксированных алфавитов) в формулах LTL-FL используются для параметризации темпоральных операторов. В этой же статье было показано, что задача проверки выполнимости формул регулярного фрагмента FL-LTL на конечных автоматах преобразователях, работающих над свободными полугруппами, разрешима со сложностью по времени, оцениваемой двойной экспонентой от размера проверяемой формулы.