E. Asarin, Equations on Timed Languages. (Уравнения для темпоризованных языков)

Мы продолжаем изучение формальных языков реального времени, распознаваемых темпоризованными (timed) автоматами Алюра и Дилла. В статье E. Asarin, O. Maler, P. Caspi, A Kleene Theorem for Timed Automata, in Proc. LICS'97 были определены темпоризованные регулярные выражения, имеющие ту же выразительную силу, что и темпоризованные автоматы. В настоящей работе вводятся квазилинейные уравнения для темпоризованных языков с регулярными коэффициентами. В работе показано, что минимальное решение такого уравнения регулярно и дан алгоритм для вычисления этого решения. Этот результат позволяет найти новое доказательство нашей "теоремы Клини" для темпоризованных автоматов. Уравнения для темпоризованных языков можно рассматривать и как новый способ спецификации таких языков. [Postscript]