P. V. Martyugin, “A lower bound for the length of the shortest carefully synchronizing words”, Izv. Vyssh. Uchebn. Zaved. Mat., 2010, Number 1,Pages <nobr>59

This article is cited in 21 papers

A lower bound for the length of the shortest carefully synchronizing words

P. V. Martyugin

Ural State University, Ekaterinburg, Russia

Abstract: We introduce a notion of careful synchronization for partial finite automata as a natural generalization of the synchronization notion for complete finite automata. We obtain a lower bound for the careful synchronization threshold for automata with a given number of states.

Keywords: finite automaton, partial finite automaton, synchronizability.

UDC: 519.713

Received: 06.12.2006