Volume 15, No 4, 2008, P. 4456
UDC 519.713.2
P. V. Martugin
Lower bounds for the length of the shortest carefully synchronizing words for two and threeletter 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 threeletter 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
email: martugin@mail.ru
