We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Exact Synchronization for Finite-State Sources.
- Authors
Travers, Nicholas; Crutchfield, James
- Abstract
We analyze how an observer synchronizes to the internal state of a finite-state information source, using the ϵ-machine causal representation. Here, we treat the case of exact synchronization, when it is possible for the observer to synchronize completely after a finite number of observations. The more difficult case of strictly asymptotic synchronization is treated in a sequel. In both cases, we find that an observer, on average, will synchronize to the source state exponentially fast and that, as a result, the average accuracy in an observer's predictions of the source output approaches its optimal level exponentially fast as well. Additionally, we show here how to analytically calculate the synchronization rate for exact ϵ-machines and provide an efficient polynomial-time algorithm to test ϵ-machines for exactness.
- Subjects
SYNCHRONIZATION; MACHINERY; ASYMPTOTES; TIME measurements; ALGORITHMS
- Publication
Journal of Statistical Physics, 2011, Vol 145, Issue 5, p1181
- ISSN
0022-4715
- Publication type
Article
- DOI
10.1007/s10955-011-0342-4