| A Note on Maximal Prefix Codes (2000) | |||||||||||||||||
Abstract | |||||||||||||||||
| A sufficient condition is established for a maximal prefix code to be synchronous. Under this condition, an upper-bound on the length of the shortest synchronizing word is established. 1 Introduction The concept of a synchronizing sequence is fundamental in automata theory, with applications in hardware testing [RHO] and mechanical parts orientation [EPP], among others. A string x is said to be a synchronizing sequence for a determininstic finite automaton M if the state reached after processing string x is the same, no matter what the starting state is. This notion was introduced in the classical paper by E.F. Moore on "gedanken experiments" on automata. Not every automaton has a synchronizing sequence. The ones that have a synchronizing sequence are called synchronizing automata. There is a simple polynomial time algorithm to decide if an automaton is synchronizing, but finding the shortest such sequence is NP-hard [EPP]. Synchronizing sequences correspond, in the semigroup of transitions... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||