Exact synchronization for finite-state sources
From MaRDI portal
Publication:658481
DOI10.1007/S10955-011-0342-4zbMATH Open1238.68058arXiv1008.4182OpenAlexW1484162783MaRDI QIDQ658481FDOQ658481
Nicholas F. Travers, James P. Crutchfield
Publication date: 12 January 2012
Published in: Journal of Statistical Physics (Search for Journal in Brave)
Abstract: We analyze how an observer synchronizes to the internal state of a finite-state information source, using the epsilon-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 epsilon-machines and provide an efficient polynomial-time algorithm to test epsilon-machines for exactness.
Full work available at URL: https://arxiv.org/abs/1008.4182
Recommendations
- Asymptotic synchronization for finite-state sources
- Quantifying communication in synchronized languages
- Synchronization and control in intrinsic and designed computation: An information-theoretic analysis of competing models of stochastic computation
- On the probability of being synchronizable
- SYNCHRONIZING TO PERIODICITY: THE TRANSIENT INFORMATION AND SYNCHRONIZATION TIME OF PERIODIC SEQUENCES
synchronizationstate estimationcausal states\(\epsilon\)-machineentropy rate convergencestate uncertainty
Cites Work
- Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
- A Mathematical Theory of Communication
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Regularities unseen, randomness observed: Levels of entropy convergence
- Synchronization and control in intrinsic and designed computation: An information-theoretic analysis of competing models of stochastic computation
- Sofic shifts with synchronizing presentations
- From finite to infinite range order via annealing: the causal architecture of deformation faulting in annealed close-packed crystals
- Asymptotic synchronization for finite-state sources
Cited In (13)
- The fundamental thermodynamic bounds on finite models
- Dealing with final state sensitivity for synchronous communication
- SYNCHRONIZING TO THE ENVIRONMENT: INFORMATION-THEORETIC CONSTRAINTS ON AGENT LEARNING
- SYNCHRONIZING TO PERIODICITY: THE TRANSIENT INFORMATION AND SYNCHRONIZATION TIME OF PERIODIC SEQUENCES
- Strong and weak optimizations in classical and quantum models of stochastic processes
- The ambiguity of simplicity in quantum and classical simulation
- Spectral simplicity of apparent complexity. I. The nondiagonalizable metadynamics of prediction
- Exponential bounds for convergence of entropy rate approximations in hidden Markov models satisfying a path-mergeability condition
- Subset synchronization and careful synchronization of binary finite automata
- Careful synchronization of partial deterministic finite automata
- Asymptotic synchronization for finite-state sources
- Computational complexity of problems for deterministic presentations of sofic shifts
- Complexity of a problem concerning reset words for Eulerian binary automata
This page was built for publication: Exact synchronization for finite-state sources
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q658481)
