A characterization of the entropies of multidimensional shifts of finite type
From MaRDI portal
(Redirected from Publication:974081)
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 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 from above. The same characterization holds for the entropies of sofic shifts. On the other hand, the entropy of an irreducible SFT is computable.
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
Cites work
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 52121 (Why is no real title available?)
- scientific article; zbMATH DE number 3574575 (Why is no real title available?)
- scientific article; zbMATH DE number 3595941 (Why is no real title available?)
- A Mathematical Theory of Communication
- An Introduction to Symbolic Dynamics and Coding
- Automorphisms of \(\mathbb Z^ d\)-subshifts of finite type
- Classification of subshifts of finite type
- Entropy bounds for constrained two-dimensional random fields
- Ergodic theory on compact spaces
- Intrinsic Markov Chains
- Mahler measure and entropy for commuting automorphisms of compact groups
- Matching rules and substitution tilings
- Non-uniqueness of measures of maximal entropy for subshifts of finite type
- On the computability of the topological entropy of subshifts
- On the entropy of \(\mathbb{Z}^d\) subshifts of finite type
- Similarity of automorphisms of the torus
- Sofic systems
- Subshifts of finite type and sofic systems
- Subsystem entropy for \(\mathbb {Z}^{d}\) sofic shifts
- Symbolic dynamics. One-sided, two-sided and countable state Markov shifts
- The entropies of topological Markov shifts and a related class of algebraic integers
- The topological entropy of cellular automata is uncomputable
- The undecidability of the domino problem
- Theory of computation of multidimensional entropy with an application to the monomer-dimer problem
- Thermodynamic Formalism
- Tilings, substitution systems and dynamical systems generated by them
- Undecidability and nonperiodicity for tilings of the plane
Cited in
(83)- 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
- 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
- The relationship between word complexity and computational complexity in subshifts
- Medvedev degrees of two-dimensional subshifts of finite type
- Approximating the hard square entropy constant with probabilistic methods
- Mixing properties of tree-shifts
- The expressiveness of quasiperiodic and minimal shifts of finite type
- Matrix characterization of multidimensional subshifts of finite type
- Subsystem entropy for \(\mathbb {Z}^{d}\) sofic shifts
- Effect of quantified irreducibility on the computability of subshift entropy
- Higher-dimensional subshifts of finite type, factor maps and measures of maximal entropy.
- An SMB approach for pressure representation in amenable virtually orderable groups
- On the absence of invariant measures with locally maximal entropy for a class of ℤ^{𝕕} shifts of finite type
- Tree-shifts: the entropy of tree-shifts of finite type
- Topological entropy and sequence entropy for Hom tree-shifts on unexpandable trees
- Representation and poly-time approximation for pressure of Z^2 lattice models in the non-uniqueness region
- Turing degree spectra of minimal subshifts
- Verification of mixing properties in two-dimensional shifts of finite type
- Probability and algorithmics: a focus on some recent developments
- 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
- 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
- Shifts of finite type with nearly full entropy
- Topological entropy of a class of subshifts of finite type
- Entropies realizable by block gluing \(\mathbb{Z}^{d}\) shifts of finite type
- Subshifts with sparse traces
- Symbolic dynamics: entropy = dimension = complexity
- Factor maps and embeddings for random \(\mathbb{Z}^d\) shifts of finite type
- Entropy dimension of shifts of finite type on free groups
- Randomness, computation and mathematics
- The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics
- Permutations with restricted movement
- Entropy dimension of shift spaces on monoids
- Characterizing entropy dimensions of minimal mutidimensional subshifts of finite type
- Random \(\mathbb{Z}^d\)-shifts of finite type
- scientific article; zbMATH DE number 5582882 (Why is no real title available?)
- Cutting corners
- Weak colored local rules for planar tilings
- Characterization of sets of limit measures of a cellular automaton iterated on a random configuration
- Effective \(S\)-adic symbolic dynamical systems
- Rauzy induction of polygon partitions and toral \(\mathbb{Z}^2\)-rotations
- Entropy on regular trees
- On the entropy of multidimensional multiplicative integer subshifts
- Interaction between cellularity of Alexandroff spaces and entropy of generalized shift maps
- On the finite-dimensional marginals of shift-invariant measures
- Complexity of shift spaces on semigroups
- Approximating entropy for a class of \(\mathbb Z^2\) Markov random fields and pressure for a class of functions on \(\mathbb Z^2\) shifts of finite type
- 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
- A generalization of the simulation theorem for semidirect products
- Beta-shifts, their languages, and computability
- Growth-type invariants for \(\mathbb Z^{d}\) subshifts of finite type and arithmetical classes of real numbers
- An integral representation for topological pressure in terms of conditional probabilities
- Direct topological factorization for topological flows
- scientific article; zbMATH DE number 7559149 (Why is no real title available?)
- The finite intersection principle and genericity
- Entropy for canonical shifts. II
- Seas of squares with sizes from a \(\Pi_{1}^{0}\) set
- Rohlin properties for \(\mathbb {Z}^{d}\) actions on the Cantor set
- A notion of effectiveness for subshifts on finitely generated groups
- Capacity of higher-dimensional constrained systems
- A characterization of topologically completely positive entropy for shifts of finite type
- Independence entropy of \(\mathbb{Z}^{d}\)-shift spaces
- On graph induced symbolic systems
- Characterizations of periods of multi-dimensional shifts
- On the computability of rotation sets and their entropies
- Slopes of multidimensional subshifts
- On the entropies of subshifts of finite type on countable amenable groups
- Markov partitions for toral \(\mathbb{Z}^2\)-rotations featuring Jeandel-Rao Wang shift and model sets
- The topological strong spatial mixing property and new conditions for pressure approximation
- Pattern generation problems arising in multiplicative integer systems
- The undecidability of the domino problem
- Entropy Bifurcation of Neural Networks on Cayley Trees
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)
