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
(98)- 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
- Effective dynamical systems beyond dimension zero and factors of SFTs
- 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
- Computability of pressure for subshifts on countable amenable groups
- Mixing properties of tree-shifts
- The expressiveness of quasiperiodic and minimal shifts of finite type
- Characterisation of the set of ground states of uniformly chaotic finite-range lattice models
- Matrix characterization of multidimensional subshifts of finite type
- Entropy of axial products on \(\mathbb{N}^d\) and trees
- Subsystem entropy for \(\mathbb {Z}^{d}\) sofic shifts
- Effect of quantified irreducibility on the computability of subshift entropy
- On a Rice theorem for dynamical properties of SFTs on groups
- 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
- Soficity of free extensions of effective subshifts
- 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
- Shifts of finite type on locally finite groups
- 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
- A remark on inverse limits of effective subshifts
- 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
- Computational characterization of surface entropies for \(\mathbb{Z}^2\) subshifts of finite type
- Complexity of shift spaces on semigroups
- Approximating entropy for a class of Z^2 Markov random fields and pressure for a class of functions on Z^2 shifts of finite type
- The spatial entropy of two-dimensional subshifts of finite type
- Translation-like actions by \(\mathbb{Z} \), the subgroup membership problem, and Medvedev degrees of effective subshifts
- Short-range and long-range order: a transition in block-gluing behavior in Hom shifts
- 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 characterization of positive entropy of Markov tree-shifts
- 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
- FO logic on cellular automata orbits equals MSO logic
- Finding lower bounds on the growth and entropy of subshifts over countable groups
- 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
- Topological structure of isolated points in the space of \(\mathbb{Z}^d\)-shifts
- 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)
