Finding Short Synchronizing Words

From LRDE

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Abstract

The problem of finding short synchronizing words is important and has many applications (part orientersroad-coloring problem, model-checking, biocomputingnetwork protocols etc.) A synchronizing word (or reset sequence) for a finite deterministic automaton is a sequence of labels which sends any state of the input automaton to a unique state. Finding the shortest synchronizing word for a general automata is NP-completeso most algorithms focus on trying to find heuristically short words in polynomial time. In this report, we will compare the different approaches used by the current state of the-art algorithms (Greedy, Cycle, SynchroP, SynchroPLand FastSynchro), in terms of space and time complexityand actual results (average lengths of found words, average time spent). We will also discuss the different intermediate representations used by these algorithms, and how we can use the information they contain.