Finding Short Synchronizing Words

From LRDE

Revision as of 17:06, 9 January 2018 by Bot (talk | contribs) (Created page with "{{CSIReport | authors = Antoine Pietri | title = Finding Short Synchronizing Words | year = 2014 | number = 1402 | abstract = The problem of finding short synchronizing words ...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.