Simulation of effective subshifts by two-dimensional subshifts of finite type
From MaRDI portal
(Redirected from Publication:368710)
Abstract: In this article we study how a subshift can simulate another one, where the notion of simulation is given by operations on subshifts inspired by the dynamical systems theory (factor, projective subaction...). There exists a correspondence between the notion of simulation and the set of forbidden patterns. The main result of this paper states that any effective subshift of dimension d -- that is a subshift whose set of forbidden patterns can be generated by a Turing machine -- can be obtained by applying dynamical operations on a subshift of finite type of dimension d + 1 -- a subshift that can be defined by a finite set of forbidden patterns. This result improves Hochman's [Hoc09].
Recommendations
- Finite State Automata Representing Two-Dimensional Subshifts
- Some notes on the classification of shift spaces: shifts of finite type; sofic shifts; and finitely defined shifts
- Finite state automata representing two-dimensional subshifts
- On the expressive power of quasiperiodic SFT
- Symbolic dynamics
- Publication:3033349
- Sofic tree-shifts
- Lattice invariants for sofic shifts
- Characterizations of periods of multi-dimensional shifts
- Algebraic aspects of symbolic dynamics
Cites work
- scientific article; zbMATH DE number 5380239 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- An Introduction to Symbolic Dynamics and Coding
- An order on sets of tilings corresponding to an order on languages
- Classification of sofic projective subdynamics of multidimensional shifts of finite type
- Complex tilings
- Endomorphisms and automorphisms of the shift dynamical system
- Fixed Point and Aperiodic Tilings
- Fixed-point tile sets and their applications
- Nonrecursive tilings of the plane. I
- Nonrecursive tilings of the plane. II
- On the dynamics and recursive properties of multidimensional symbolic systems
- Symbolic dynamics. One-sided, two-sided and countable state Markov shifts
- The undecidability of the domino problem
- Tilings, substitution systems and dynamical systems generated by them
- Undecidability and nonperiodicity for tilings of the plane
Cited in
(43)- Ergodic optimization in dynamical systems
- Subsystem entropies of shifts of finite type and sofic shifts on countable amenable groups
- Arithmetical hierarchy of the Besicovitch-stability of noisy tilings
- Hardness of conjugacy, embedding and factorization of multidimensional subshifts of finite type
- Effective closed subshifts in 1D can be implemented in 2D
- Recognizability of morphisms
- The expressiveness of quasiperiodic and minimal shifts of finite type
- On the expressive power of quasiperiodic SFT
- Computability in Symbolic Dynamics
- Turing degree spectra of minimal subshifts
- Probability and algorithmics: a focus on some recent developments
- Quantified block gluing for multidimensional subshifts of finite type: aperiodicity and entropy
- Computability of topological pressure on compact shift spaces beyond finite type*
- Parametrization by horizontal constraints in the study of algorithmic properties of \(\mathbb{Z}^2\)-subshifts of finite type
- On the induction operation for shift subspaces and cellular automata as presentations of dynamical systems
- On the Besicovitch-stability of noisy random tilings
- Entropies realizable by block gluing \(\mathbb{Z}^{d}\) shifts of finite type
- Subshifts with sparse traces
- A class of nonsofic multidimensional shift spaces
- The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics
- One-dimensional projective subdynamics of uniformly mixing shifts of finite type
- Quantifier extensions of multidimensional sofic shifts
- 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
- Finite State Automata Representing Two-Dimensional Subshifts
- Realtime subshifts
- On the dynamics and recursive properties of multidimensional symbolic systems
- Algorithmic complexity for the realization of an effective subshift by a sofic
- Zero-temperature chaos in bidimensional models with finite-range potentials
- A generalization of the simulation theorem for semidirect products
- Projective subdynamics and universal shifts
- Automatic winning shifts
- The group of reversible Turing machines
- Computability of topological entropy: from general systems to transformations on Cantor sets and the interval
- scientific article; zbMATH DE number 7559149 (Why is no real title available?)
- Hardness of conjugacy, embedding and factorization of multidimensional subshifts
- Seas of squares with sizes from a \(\Pi_{1}^{0}\) set
- A notion of effectiveness for subshifts on finitely generated groups
- Zero-temperature phase diagram for double-well type potentials in the summable variation class
- Classification of sofic projective subdynamics of multidimensional shifts of finite type
- Slopes of multidimensional subshifts
- Countable sofic shifts with a periodic direction
This page was built for publication: Simulation of effective subshifts by two-dimensional subshifts of finite type
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q368710)
