Exact synchronization for finite-state sources
From MaRDI portal
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.
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
Cites work
- scientific article; zbMATH DE number 3719745 (Why is no real title available?)
- scientific article; zbMATH DE number 1517989 (Why is no real title available?)
- scientific article; zbMATH DE number 3371972 (Why is no real title available?)
- A Mathematical Theory of Communication
- Asymptotic synchronization for finite-state sources
- Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
- From finite to infinite range order via annealing: the causal architecture of deformation faulting in annealed close-packed crystals
- Regularities unseen, randomness observed: Levels of entropy convergence
- Sofic shifts with synchronizing presentations
- Synchronization and control in intrinsic and designed computation: An information-theoretic analysis of competing models of stochastic computation
Cited in
(14)- Strong and weak optimizations in classical and quantum models of stochastic processes
- Subset synchronization and careful synchronization of binary finite automata
- Computational complexity of problems for deterministic presentations of sofic shifts
- Exponential bounds for convergence of entropy rate approximations in hidden Markov models satisfying a path-mergeability condition
- Spectral simplicity of apparent complexity. I: The nondiagonalizable metadynamics of prediction
- Careful synchronization of partial deterministic finite automata
- Asymptotic synchronization for finite-state sources
- The ambiguity of simplicity in quantum and classical simulation
- Complexity of a problem concerning reset words for Eulerian binary automata
- The fundamental thermodynamic bounds on finite models
- SYNCHRONIZING TO PERIODICITY: THE TRANSIENT INFORMATION AND SYNCHRONIZATION TIME OF PERIODIC SEQUENCES
- SYNCHRONIZING TO THE ENVIRONMENT: INFORMATION-THEORETIC CONSTRAINTS ON AGENT LEARNING
- Dealing with final state sensitivity for synchronous communication
- Synchronization and control in intrinsic and designed computation: An information-theoretic analysis of competing models of stochastic computation
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)
