computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

, more precisely, in the theory of

deterministic finite automata In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state auto ...

(DFA), a synchronizing word or reset sequence is a word in the input alphabet of the DFA that sends any state of the DFA to one and the same state.Avraham Trakhtman
''Synchronizing automata, algorithms, Cerny Conjecture''
Accessed May 15, 2010. That is, if an ensemble of copies of the DFA are each started in different states, and all of the copies process the synchronizing word, they will all end up in the same state. Not every DFA has a synchronizing word; for instance, a DFA with two states, one for words of even length and one for words of odd length, can never be synchronized.

Existence

Given a DFA, the problem of determining if it has a synchronizing word can be solved in

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

using a theorem due to Ján Černý. A simple approach considers the power set of states of the DFA, and builds a directed graph where nodes belong to the power set, and a directed edge describes the action of the transition function. A path from the node of all states to a singleton state shows the existence of a synchronizing word. This algorithm is

exponential Exponential may refer to any of several mathematical topics related to exponentiation, including: * Exponential function, also: **Matrix exponential, the matrix analogue to the above *Exponential decay, decrease at a rate proportional to value * Ex ...

in the number of states. A polynomial algorithm results however, due to a theorem of Černý that exploits the substructure of the problem, and shows that a synchronizing word exists if and only if every pair of states has a synchronizing word.

Length

The problem of estimating the length of synchronizing words has a long history and was posed independently by several authors, but it is commonly known as the Černý conjecture. In 1969, Ján Černý conjectured that (''n'' − 1)² is the

upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of . Dually, a lower bound or minorant of is defined to be an element of that is less ...

for the length of the shortest synchronizing word for any ''n''-state complete DFA (a DFA with complete state transition graph). If this is true, it would be tight: in his 1964 paper, Černý exhibited a class of automata (indexed by the number ''n'' of states) for which the shortest reset words have this length. (in Slovak). The best upper bound known is 0.1654''n''³, far from the lower bound. For ''n''-state DFAs over a ''k''-letter input alphabet, an algorithm by

David Eppstein David Arthur Eppstein (born 1963) is an American computer scientist and mathematician. He is a distinguished professor of computer science at the University of California, Irvine. He is known for his work in computational geometry, graph algor ...

finds a synchronizing word of length at most 11''n''³/48 + O(''n''²), and runs in

time complexity In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...

O(''n''³+''kn''²). This algorithm does not always find the shortest possible synchronizing word for a given automaton; as Eppstein also shows, the problem of finding the shortest synchronizing word is

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

. However, for a special class of automata in which all state transitions preserve the

cyclic order In mathematics, a cyclic order is a way to arrange a set of objects in a circle. Unlike most structures in order theory, a cyclic order is not modeled as a binary relation, such as "". One does not say that east is "more clockwise" than west. Ins ...

of the states, he describes a different algorithm with time O(''kn''²) that always finds the shortest synchronizing word, proves that these automata always have a synchronizing word of length at most (''n'' − 1)² (the bound given in Černý's conjecture), and exhibits examples of automata with this special form whose shortest synchronizing word has length exactly (''n'' − 1)².

Road coloring

The road coloring problem is the problem of labeling the edges of a regular directed graph with the symbols of a ''k''-letter input alphabet (where ''k'' is the outdegree of each vertex) in order to form a synchronizable DFA. It was conjectured in 1970 by Benjamin Weiss and Roy Adler that any

strongly connected In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of a directed graph form a partition into subgraphs that are thems ...

and

aperiodic A periodic function, also called a periodic waveform (or simply periodic wave), is a function that repeats its values at regular intervals or periods. The repeatable part of the function or waveform is called a ''cycle''. For example, the tr ...

regular digraph can be labeled in this way; their conjecture was proven in 2007 by Avraham Trahtman.

Related: transformation semigroups

transformation semigroup In algebra, a transformation semigroup (or composition semigroup) is a collection of transformations ( functions from a set to itself) that is closed under function composition. If it includes the identity function, it is a monoid, called a tra ...

is ''synchronizing'' if it contains an element of rank 1, that is, an element whose image is of cardinality 1.. A DFA corresponds to a transformation semigroup with a distinguished generator set.

Existence

Length

Road coloring

Related: transformation semigroups

References

Further reading