Exact synchronization in partial deterministic automata

Abstract

An automaton is a synchronizing if it has an input word that transfers it from any state to a particular state. There are two versions of synchronization in partial deterministic automata: Careful synchronization and exact synchronization. In this paper we focus on the exact version; we survey the complexity of testing exact synchronization and describe a SAT solver based algorithm for calculating the length of the shortest exact synchronizing word. © Published under licence by IOP Publishing Ltd.