Бурдонов И.Б., Косачев А.С., Кулямин В.В. Асинхронные автоматы: Классификация и тестирование

М.: Институт Системного Программирования РАН. – 60 с. Рассматриваются конечные автоматы, отличающиеся от классического автомата Мили тем, что переход осуществляется либо по приему стимула (входного символа), либо по выдаче реакции (выходного символа), причем в каждом состоянии выбор одного из допустимых переходов недетерминирован. Такими автоматами являются автоматы с отложенной реакцией (АОР), в которых переход по стимулу выполняется всегда, когда этот стимул имеется на входе автомата, и автоматы ввода-вывода (IOSM - Input/Output State Machines), в которых переход по выдаче реакции допустим независимо от наличия стимула, а не принятый в этом состоянии стимул может быть принят позже, в другом состоянии. Обобщением этих классов автоматов является асинхронный автомат, в котором допускаются также переходы по отсутствию стимула. Предлагается классификация асинхронных автоматов, основанная на реализуемой автоматом словарной функции и эквивалентности автоматов с совпадающей словарной функцией. Показывается, что класс всех асинхронных автоматов эквивалентен своему подклассу автоматов с отложенными реакциями, а словарные функции автоматов ввода-вывода образуют собственное подмножество всех автоматных словарных функций. С автоматом связывается также множество сериализаций (смешанных последовательностей воспринимаемых стимулов и выдаваемых реакций), и исследуется его связь со словарной функцией. Работа завершается обзором основных проблем тестирования соответствия, когда асинхронные автоматы используются как спецификационная модель программных и аппаратных систем.