К синтезу синхронизирующих и установочных последовательностей для входо-выходных полуавтоматов

Евтушенко, Нина Владимировна; Бурдонов, Игорь Борисович; Косачев, Александр Сергеевич; Кушик, Наталья Геннадьевна

К синтезу синхронизирующих и установочных последовательностей для входо-выходных полуавтоматов

Евтушенко, Нина Владимировна, Бурдонов, Игорь Борисович, Косачев, Александр Сергеевич, Кушик, Наталья Геннадьевна

Дата публикации: 2017

Дата публикации в реестре: 2020-03-03T18:28:19Z

Аннотация:

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

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

Тип: статьи в журналах

Источник: Моделирование и анализ информационных систем. 2017. Т. 24, № 6. С. 730-742