Exact synchronization for finite-state sources (Q658481)

The synchronization process for a class of finite-state hidden Markov models, the \(\epsilon\)-machines, is analyzed. An \(\epsilon\)-machine is exactly synchronizable if the observer synchronizes to almost every sequence generated by the machine in finite time. One proves that an observer synchronizes exactly to the internal state of any \(\epsilon \)-machine exponentially fast. The synchronization rate can be computed analytically. The observers average uncertainty in the machine state as well as the average uncertainty in predictions of the future symbols decay exponentially fast. At the end of the article, necessary and sufficient conditions for exactness of an \(\epsilon\)-machine together with a test-algorithm are provided.