Quasioptimal bound for the length of reset words for regular automata. (English) Zbl 0844.68085

Rystsov, I. K.

Acta Cybern. 12, No. 2, 145-152 (1995).

Summary: J. Černý [Mat.-Fyz. Cas., Slovensk. Akad. Vied 14, 208-216 (1964; Zbl 0137.01101)] stated the hypothesis that in a finite reset automaton with \(n\) states there is a reset (synchronizing) word whose length is at most \((n- 1)^2\) and showed that this bound can be achieved. In J. Černý, A. Pirická and B. Rosenauerová [Kybernetika, Praha 7, 289-298 (1971; Zbl 0223.94029)] this hypotheses was proved by direct enumeration of automata with small number of states. J. Pin used algebraic methods to prove this hypothesis for cyclic automata with prime number of states. The general upper bound \((n^3- n)/6\) has been obtained by A. A. Klyachko, the author and M. A. Spivak [Kibernetika 1987, No. 2, 16-20 (1987; Zbl 0691.05025)] for any reset \(n\)-state automaton.
The aim of this paper is to obtain the quasioptimal bound \(2\cdot (n- 1)^2\) for regular reset automata with \(n\) states and to extend the class of automata for which the optimal bound is valid.

MSC:

68Q45

Formal languages and automata

Keywords:

cyclic automata; regular reset automata

Citations:

Zbl 0137.01101; Zbl 0223.94029; Zbl 0691.05025