Эксперименты с недетерминированными автоматами. Методы синтеза установочных и различающих экспериментов

      Аннотация: Монография продолжает исследования, начатые более полувека назад и посвященные синтезу умозрительных экспериментов с конечными автоматами. Под экспериментом понимается подача входной последовательности на автомат, наблюдение выходной реакции и вывод заключения о свойствах автомата. Монография посвящена исследованию и разработке методов синтеза установочных и различающих экспериментов с недетерминированными автоматами. Такие эксперименты позволяют определить финальное и начальное состояния автомата. Рассматриваются безусловные и условные установочные и различающие эксперименты с полностью определенными наблюдаемыми недетерминированными автоматами, устанавливаются необходимые и достаточные условия существования таких экспериментов, и предлагаются методы их синтеза. Приводятся различные технические приложения недетерминированных автоматов, в частности, рассматриваются эксперименты по синтезу проверяющих тестов для протокольных реализаций, а также эксперименты по упрощению компоненты автоматной сети, в том числе, с целью оптимизации логических схем. Монография может быть полезна лицам, заинтересованным в более глубоком изучении теории автоматов.

Ключевые слова: недетерминированные автоматы, умозрительные эксперименты, безусловные и условные эксперименты, различающие и установочные эксперименты