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

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