Volume 15, No 4, 2008, P. 44-56

UDC 519.713.2
P. V. Martugin
Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata

Abstract:
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. M. Gorky Ural State University,
51 Lenin ave., 620083 Ekaterinburg, Russia
e-mail: martugin@mail.ru