Some Variants of the Problem of Synchronization of Automata

Certain variations of the firing-squad synchronization problem posed by J. Myhill [E. F. Moore, The Firing Squad Synchronization Problem, in Sequential Machines, Reading, Mass., Addison-Wesley, 1964, pp. 213–214] are considered. The synchronization problem is solved for the case when the starting signal is given to an arbitrary automaton in the chain. It is shown that in this case the chain is synchronized within the time $2n-2-a_{\text{мин}}$, where $n$ is the length of the chain, and $a_{\text{мин}}$ is the minimum distance from the first automaton to the end of the chain. The obtained solution is a modification of the solution obtained by Levenshtein for the Myhill problem [Probl. Peredachi Inf., 1965, vol. 1, no. 4, pp. 20–32]; each of the automata has ten internal states. The existence of a solution is shown for the case when the objects to be synchronized have different firing times.