Test for synchronizability of finite automata and variable length codes
Shimon Even · IEEE Transactions on Information Theory · 1964
A finite automation is called synchronizable ofNth order if the knowledge of the lastNoutputs suffices to determine the state of the automaton at one time during the lastNoutputs (including the initial and the final states). In an analogous manner synchronizability ofNth order is defined for variable length codes. The paper describes a test for synchronizability on a more general model, the coding graphs, and shows that finite automata and variable length codes are special cases of it.