Асинхронные автоматы: классификация и тестирование.
News
Асинхронные автоматы: классификация и тестирование.
Abstract
В статье рассматриваются конечные автоматы, отличающиеся от классического автомата Мили тем, что переход осуществляется либо по приему стимула (входного символа), либо по выдаче реакции (выходного символа), причем в каждом состоянии выбор одного из допустимых переходов недетерминирован. Такими автоматами являются автоматы с отложенной реакцией (АОР), в которых переход по стимулу выполняется всегда, когда этот стимул имеется на входе автомата, и автоматы ввода- вывода (IOSM - Input/Output State Machines), в которых переход по выдаче реакции допустим независимо от наличия стимула, в то время как, принятый в этом состоянии стимул может быть принят позже, в другом состоянии. Обобщением этих классов автоматов является асинхронный автомат, в котором допускаются также переходы по отсутствию стимула. Предлагается классификация асинхронных автоматов, основанная на реализуемой автоматом словарной функции и эквивалентности автоматов с совпадающей словарной функцией. Показывается, что класс всех асинхронных автоматов эквивалентен своему подклассу автоматов с отложенными реакциями, а словарные функции автоматов ввода-вывода образуют собственное подмножество всех автоматных словарных функций. С автоматом связывается также множество сериализаций (смешанных последовательностей воспринимаемых стимулов и выдаваемых реакций), и исследуется его связь со словарной функцией. Статья завершается обзором основных проблем тестирования соответствия, когда асинхронные автоматы используются как спецификационная модель программных и аппаратных систем.
Edition
Proceedings of the Institute for System Programming, vol. 4 (in Russian), 2003, Стр. 7-83.
ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).
For citation
Full text of the paper in pdf (in Russian)
Back to the contents of the volume