Let's take a simple 3-state automaton :
Synchronization checks
We can check that is synchronizing:
We can guess from the figure that is a synchronizing word of . We can verify that with is_synchronized_by
:
Algorithms
To find a short synchronizing word, use the synchronizing_word()
method. It takes an algorithm as argument, defaulting to greedy
.
Greedy
Eppstein's greedy is a greedy algorithm which always synchronizes the closest pair first. It can be called using synchronizing_word('greedy')
or synchronizing_word('eppstein')
Cycle
Cycle is a algorithm similar to Greedy, which ensures that the pair synchronized contains the latest singleton in which the synchronization previously took place. This is less efficient in the general case but gives optimal results () for Černý automata.
SynchroP & SynchroPL
SynchroP is a "one-step ahead" heuristic with a time complexity that checks the distance of the new active states from after synchronizing a specific pair, and tries to minimize the sum of these distances.
SynchroPL is similar to SynchroP but adds the distance of the synchronized pair as a "cost" in the heuristic. Its time complexity is also .
FastSynchro
FastSynchro finds labels that reduce the new distances of the active states when appended to the synchronizing word. To guarantee that the algorithm terminates, it is only used if the label reduces the overall distance. If not, a bounded SynchroPL heuristic is used. The complexity of this algorithm is .
Synchronizing words for transducers
All the algorithms can also be used with k-tapes automata: