Аннотация доклада.

Многие проблемы, связанные с (дискретными) управляющими системами, можно свести к решению уравнения A @ X ~ S для автоматных моделей, где X - свободная переменная, A – контекст, @ - оператор композиции, и ~ – отношение конформности. В большинстве известных работ рассматриваются уравнения относительно операций синхронной и параллельной композиции. Синхронная композиция соответствует «мгновенной» связи между компонентами системы. Параллельная композиция соответствует асинхронному взаимодействию, допускающему произвольную задержку между событиями, и используется в телекоммуникационных системах. В качестве отношений конформности рассматриваются отношения редукции и эквивалентности между автоматами, и, соответственно можно говорить об автоматных синхронных и параллельных неравенствах и уравнениях.

В [1] разработана теория для решения синхронных и параллельных неравенств и уравнений над формальными языками. В частности, неравенства и уравнения в алгебре регулярных языков эффективно решаются на основе конечно автоматных операторов. В некоторых приложениях могут потребоваться подмножества решений, имеющие дополнительные свойства. Соответственно, мы рассматриваем различные виды частных решений, таких как комбинационные решения, полностью определенные решения, прогрессивные решения и др.

Комбинационное решение эквивалентно автомату с одним состоянием и может быть использовано для разработки выигрышных / не проигрышных стратегий в логических играх, в то время как композиция контекста с прогрессивным решением не имеет тупиков и / или осцилляций. Для каждого вида вышеуказанных решений можно предложить методику получения соответствующего наибольшего решения. Полученные результаты можно распространить на решение уравнений для многокомпонентных композиций и относительно других операторов композиции.

[1] T. Villa, N. Yevtushenko, R. K. Brayton, A. Mishchenko, A. Petrenko, A. Sangiovanni-Vincentelli. The Unknown Component Problem. Springer, 2012.