Article ID Journal Published Year Pages File Type
435512 Theoretical Computer Science 2009 17 Pages PDF
Abstract

Most complete binary prefix codes have a synchronizing string, that is a string that resynchronizes the decoder regardless of its previous state. This work presents an upper bound on the length of the shortest synchronizing string for such codes. Two classes of codes with a long shortest synchronizing string are presented. It is known that finding a synchronizing string for a code is equivalent to finding a synchronizing string of some finite automaton. The Černý conjecture for this class of automata is discussed.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics