This Second Edition maintains the introductory character of the original 1995 edition as a general textbook on symbolic dynamics and its applications to coding. It has established strong connections with many areas, including linear algebra, graph theory, probability, group theory, and the theory of computation, as well as data storage, statistical mechanics, and $C^*$-algebras. Symbolic dynamics is a mature yet rapidly developing area of dynamical systems. On the expository side, we present a short proof of Chung's variational principle for sofic topological pressure. We also prove that for any group-shift over a sofic group, the Haar measure is the unique measure of maximal sofic entropy for every sofic approximation sequence, as long as the homoclinic group is dense. As applications of our main result we present a criterion for uniqueness of an equilibrium measure, as well as sufficient conditions for having that the equilibrium states do not depend upon the chosen sofic approximation sequence. This extends a classical theorem of Lanford and Ruelle, as well as previous generalizations of Ollangier, Pinchon, Tempelman and others, to the case where the group is sofic. We show that for any sufficiently regular potential $f \colon X \to \mathbb$, any translation-invariant Borel probability measure on $X$ which maximizes the measure-theoretical sofic pressure of $f$ with respect to $\Sigma$, is a Gibbs state with respect to $f$. Further assume that $X$ is a shift of finite type, or more generally, that $X$ satisfies the topological Markov property.
Let $\Gamma$ be a sofic group, $\Sigma$ be a sofic approximation sequence of $\Gamma$ and $X$ be a $\Gamma$-subshift with nonnegative sofic topological entropy with respect to $\Sigma$. We also suggest a procedure of constructing an $\epsilon$-recoverable measure from a corresponding deterministic system, and prove that for small $\epsilon$ the constructed measure is a maximizer of the metric entropy. Drawing on tools from ergodic theory, we prove some properties of entropy-maximizing measures. In the second part of the paper we consider a modification of the problem wherein the entries in the sequence are viewed as random variables over a finite alphabet that follow some joint distribution, and the recovery condition requires that the Shannon entropy of the $k$-tuple conditioned on its $l$-neighborhood be bounded above by some $\epsilon>0.$ We study properties of measures on infinite sequences that maximize the metric entropy under the recoverability condition.
The techniques that we employ rely on the connection of this problem with constrained systems. We address the problem of finding the maximum growth rate of the set, which we term capacity, as well as constructions of explicit families that approach the optimal rate. If ∑ ⊆ AG is a strongly irreducible subshift of finite type, we endow a locally compact and Hausdorff topology on the homoclinic equivalence relation \( \right)\), G).Motivated by the established notion of storage codes, we consider sets of infinite sequences over a finite alphabet such that every $k$-tuple of consecutive entries is uniquely recoverable from its $l$-neighborhood in the sequence. Let G be an infinite countable group and A be a finite set. We also consider dual surjunctive systems for more general dynamical systems, namely for certain expansive algebraic actions, employing results of Chung and Li.
Moreover we show that dual surjunctive groups are closed under ultraproducts, under elementary equivalence, and under certain semidirect products (using the ideas of Arzhantseva and Gal for the latter) they form a closed subset in the space of marked groups, fully residually dual surjunctive groups are dual surjunctive, etc.
#Irreducible subshift full#
By quantifying the notions of injectivity and post-surjectivity for cellular automata, we show that the image of the full topological shift under an injective cellular automaton is a subshift of finite type in a quantitative way. We show that dual surjunctive groups satisfy Kaplansky's direct finiteness conjecture for all fields of positive characteristic. We explore the dual version of Gottschalk's conjecture recently introduced by Capobianco, Kari, and Taati, and the notion of dual surjunctivity in general.
0 kommentar(er)
