E. Asarin, O. Maler, P. Caspi, A Kleene Theorem for Timed Automata. (Теорема Клини для темпоризованных автоматов)

В статье определены темпоризованные регулярные выражения – обобщение обычных регулярных выражений на случай множеств дискретнозначных сигналов с непрерывным временем. Установлено, что этот формализм имеет ту же выразительную силу, что и темпоризованные (timed) автоматы Алюра и Дилла. Описаны алгоритмы для перехода от выражений к автоматам и обратно. Результат также распространен на омега-регулярные выражения (теорема Бюхи). [Postscript]