Colloquium Mathematics - Dr. H. Don

Title:
Synchronization of deterministic and partial automata

Abstract:
An automaton is a directed graph with labeled edges.The vertices represent states in which the automaton can be. The labels serve as input to bring the automaton to an other state.

In a deterministic automaton, for each label there is exactly one outgoing edge from each state. Given the starting state and a sequence of labels (input word), there is a unique way to follow the edges with these labels, leading to the state of the automaton after reading the input word. If there exists a word for which the final state does not depend on the starting state, the automaton is called synchronizing. For a synchronizing automaton, one can ask for the length of the shortest synchronizing word. In this talk I will show that this length is at most cubic in the number of states.

In a partial automaton, for each label there is at most one outgoing edge from each state. If the automaton is in a state with zero outgoing edges with a particular label, then this label is forbidden as input. Still there might exist a synchronizing word which for each starting state avoids all forbidden input. However, in this case the shortest synchronizing word can have length exponential in the number of states, for which a construction will be presented.

Joint work with Hans Zantema and Michiel de Bondt.