Volume 15, No 4, 2008, P. 44-56
P. V. Martugin
Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata
The notion of carefully synchronizing words for partial finite automata (PFA) is introduced. The careful synchronization of PFA is a natural generalization of the synchronization of the deterministic finite automata. Some lower bounds for the length of the shortest carefully synchronizing words are found for an automaton with a given number of states. It is proven that the maximal length of the shortest reset words for two- and three-letter automata grows faster than any polynomial in the number of states.
Tabl. 1, illustr. 3, bibl. 11.
Keywords: automata, synchronization.
Martugin Pavel Vladimirovich 1
1. M. Gorky Ural State University,
51 Lenin ave., 620083 Ekaterinburg, Russia