A characterization of the entropies of multidimensional shifts of finite type

DOI10.4007/ANNALS.2010.171.2011zbMATH Open1192.37022arXivmath/0703206OpenAlexW3098115869MaRDI QIDQ974081FDOQ974081

Michael Hochman, Tom Meyerovitch

Publication date: 27 May 2010

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Abstract: We show that the values of entropies of multidimensional shifts of finite type (SFTs) are characterized by a certain computation-theoretic property: a real number $hgeq0$ is the entropy of such an SFT if and only if it is right recursively enumerable, i.e. there is a computable sequence of rational numbers converging to $h$ from above. The same characterization holds for the entropies of sofic shifts. On the other hand, the entropy of an irreducible SFT is computable.

Full work available at URL: https://arxiv.org/abs/math/0703206

Recommendations

• Topological entropy of a class of subshifts of finite type
• Perturbations of multidimensional shifts of finite type
• Characterizing entropy dimensions of minimal mutidimensional subshifts of finite type
• Densities and entropies in cellular automata
• Entropies realizable by block gluing \(\mathbb{Z}^{d}\) shifts of finite type

zbMATH Keywords

entropyshift of finite type

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Symbolic dynamics (37B10) Topological entropy (37B40) Computational methods for ergodic theory (approximation of invariant measures, computation of Lyapunov exponents, entropy, etc.) (37M25)

Cites Work

• A Mathematical Theory of Communication
• Ergodic theory on compact spaces
• Subshifts of finite type and sofic systems
• Title not available (Why is that?)
• Thermodynamic Formalism
• An Introduction to Symbolic Dynamics and Coding
• Intrinsic Markov Chains
• Mahler measure and entropy for commuting automorphisms of compact groups
• Symbolic dynamics. One-sided, two-sided and countable state Markov shifts
• Title not available (Why is that?)
• Title not available (Why is that?)
• Similarity of automorphisms of the torus
• On the entropy of \(\mathbb{Z}^d\) subshifts of finite type
• The undecidability of the domino problem
• The topological entropy of cellular automata is uncomputable
• Title not available (Why is that?)
• The entropies of topological Markov shifts and a related class of algebraic integers
• Non-uniqueness of measures of maximal entropy for subshifts of finite type
• Matching rules and substitution tilings
• Undecidability and nonperiodicity for tilings of the plane
• Tilings, substitution systems and dynamical systems generated by them
• Classification of subshifts of finite type
• Theory of computation of multidimensional entropy with an application to the monomer-dimer problem
• Title not available (Why is that?)
• Automorphisms of \(\mathbb Z^ d\)-subshifts of finite type
• Sofic systems
• Entropy bounds for constrained two-dimensional random fields
• Subsystem entropy for \(\mathbb {Z}^{d}\) sofic shifts

Cited In (80)

• Arithmetical hierarchy of the Besicovitch-stability of noisy tilings
• Mass problems associated with effectively closed sets
• On structure of topological entropy for tree-shift of finite type
• On spatial entropy of multi-dimensional symbolic dynamical systems
• Medvedev degrees of two-dimensional subshifts of finite type
• The relationship between word complexity and computational complexity in subshifts
• Mixing properties of tree-shifts
• Approximating the hard square entropy constant with probabilistic methods
• Approximating entropy for a class of ℤ²Markov random fields and pressure for a class of functions on ℤ²shifts of finite type
• Effect of quantified irreducibility on the computability of subshift entropy
• Higher-dimensional subshifts of finite type, factor maps and measures of maximal entropy.
• Tree-shifts: the entropy of tree-shifts of finite type
• An SMB approach for pressure representation in amenable virtually orderable groups
• Turing degree spectra of minimal subshifts
• Representation and poly-time approximation for pressure of \(\mathbb Z^2\) lattice models in the non-uniqueness region
• On the topological entropy of subshifts of finite type on free semigroups
• Quantified block gluing for multidimensional subshifts of finite type: aperiodicity and entropy
• Computability of topological pressure on compact shift spaces beyond finite type*
• Computability at zero temperature
• Entropies realizable by block gluing \(\mathbb{Z}^{d}\) shifts of finite type
• Symbolic dynamics: entropy = dimension = complexity
• Entropy dimension of shifts of finite type on free groups
• The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics
• Permutations with restricted movement
• Characterizing entropy dimensions of minimal mutidimensional subshifts of finite type
• Title not available (Why is that?)
• Cutting corners
• Random \(\mathbb{Z}^d\)-shifts of finite type
• On the computability of rotation sets and their entropies
• Weak colored local rules for planar tilings
• Characterization of sets of limit measures of a cellular automaton iterated on a random configuration
• On the finite-dimensional marginals of shift-invariant measures
• On the entropy of multidimensional multiplicative integer subshifts
• Rauzy induction of polygon partitions and toral \(\mathbb{Z}^2\)-rotations
• Entropy on regular trees
• Complexity of shift spaces on semigroups
• The spatial entropy of two-dimensional subshifts of finite type
• On the dynamics and recursive properties of multidimensional symbolic systems
• On the zero-temperature limit of Gibbs states
• The structure of limit sets for \(\mathbb{Z}^d\) actions
• Randomness, Computation and Mathematics
• A generalization of the simulation theorem for semidirect products
• An integral representation for topological pressure in terms of conditional probabilities
• Beta-shifts, their languages, and computability
• Growth-type invariants for \(\mathbb Z^{d}\) subshifts of finite type and arithmetical classes of real numbers
• Title not available (Why is that?)
• The finite intersection principle and genericity
• Seas of squares with sizes from a \(\Pi_{1}^{0}\) set
• Entropy for canonical shifts. II
• Matrix Characterization of Multidimensional Subshifts of Finite Type
• Rohlin properties for \(\mathbb {Z}^{d}\) actions on the Cantor set
• A characterization of topologically completely positive entropy for shifts of finite type
• A notion of effectiveness for subshifts on finitely generated groups
• Characterizations of periods of multi-dimensional shifts
• Independence entropy of \(\mathbb{Z}^{d}\)-shift spaces
• The Undecidability of the Domino Problem
• Slopes of multidimensional subshifts
• On the entropies of subshifts of finite type on countable amenable groups
• The topological strong spatial mixing property and new conditions for pressure approximation
• Markov partitions for toral \(\mathbb{Z}^2\)-rotations featuring Jeandel-Rao Wang shift and model sets
• Pattern generation problems arising in multiplicative integer systems
• Entropy Bifurcation of Neural Networks on Cayley Trees
• Characterization for entropy of shifts of finite type on Cayley trees
• Multidimensional sofic shifts without separation and their factors
• Subsystem entropies of shifts of finite type and sofic shifts on countable amenable groups
• The expressiveness of quasiperiodic and minimal shifts of finite type
• Capacity of Higher-Dimensional Constrained Systems
• Topological entropy and sequence entropy for Hom tree-shifts on unexpandable trees
• On the absence of invariant measures with locally maximal entropy for a class of ℤ^{𝕕} shifts of finite type
• Verification of mixing properties in two-dimensional shifts of finite type
• Probability and algorithmics: a focus on some recent developments
• Parametrization by horizontal constraints in the study of algorithmic properties of \(\mathbb{Z}^2\)-subshifts of finite type
• A complete proof that square ice entropy is
• Subshifts with sparse traces
• Factor maps and embeddings for random \(\mathbb{Z}^d\) shifts of finite type
• Entropy dimension of shift spaces on monoids
• Interaction between cellularity of Alexandroff spaces and entropy of generalized shift maps
• Direct topological factorization for topological flows
• Effective S-adic Symbolic Dynamical Systems
• On graph induced symbolic systems

This page was built for publication: A characterization of the entropies of multidimensional shifts of finite type

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q974081)