Exact synchronization for finite-state sources
From MaRDI portal
(Redirected from Publication:658481)
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
(15)- The fundamental thermodynamic bounds on finite models
- An improved algorithm for finding the shortest synchronizing words
- Dealing with final state sensitivity for synchronous communication
- SYNCHRONIZING TO THE ENVIRONMENT: INFORMATION-THEORETIC CONSTRAINTS ON AGENT LEARNING
- Strong and weak optimizations in classical and quantum models of stochastic processes
- SYNCHRONIZING TO PERIODICITY: THE TRANSIENT INFORMATION AND SYNCHRONIZATION TIME OF PERIODIC SEQUENCES
- The ambiguity of simplicity in quantum and classical simulation
- Synchronization and control in intrinsic and designed computation: An information-theoretic analysis of competing models of stochastic computation
- 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
- Spectral simplicity of apparent complexity. I: The nondiagonalizable metadynamics of prediction
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)
