Deriving Synchronizing and Homing Sequences for Input/Output Automata

摘要

The paper considers the problems of checking the existence and synthesis of synchronizing and homing sequences for finite input/output automata. The relevant sequences can be used when identifying the state of the system under consideration after applying the proper input sequence. In the model considered in the study, the actions are divided into inputs and outputs, however, there are no explicitly specified sets of initial and final states. The article defines the concepts of synchronizing and homing sequences and suggests methods for their synthesis for a special class of input/output automata, which have transitions in each state on either input or output actions; in addition, there are no cycles marked with output symbols in the corresponding transition graph. The necessary and sufficient conditions of existence of synchronizing and homing sequences are established, and the length of such sequences is estimated for the described class of input/output automata. The subclasses of automata are specified, for which the worst (mainly, exponential) complexity cases are not reachable.