Simulation of effective subshifts by two-dimensional subshifts of finite type
From MaRDI portal
Publication:368710
DOI10.1007/S10440-013-9808-5zbMATH Open1283.37014arXiv1602.06095OpenAlexW2052038522MaRDI QIDQ368710FDOQ368710
Authors: Nathalie Aubrun, Mathieu Sablik 
Publication date: 23 September 2013
Published in: Acta Applicandae Mathematicae (Search for Journal in Brave)
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].
Full work available at URL: https://arxiv.org/abs/1602.06095
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
symbolic dynamicsTuring machineeffectively closed subshiftfactor systemhigher-dimensional subshiftsubaction
Cites Work
- An Introduction to Symbolic Dynamics and Coding
- Endomorphisms and automorphisms of the shift dynamical system
- Symbolic dynamics. One-sided, two-sided and countable state Markov shifts
- Title not available (Why is that?)
- The undecidability of the domino problem
- Title not available (Why is that?)
- On the dynamics and recursive properties of multidimensional symbolic systems
- Undecidability and nonperiodicity for tilings of the plane
- Tilings, substitution systems and dynamical systems generated by them
- Fixed Point and Aperiodic Tilings
- Nonrecursive tilings of the plane. I
- Nonrecursive tilings of the plane. II
- Fixed-point tile sets and their applications
- Complex tilings
- Classification of sofic projective subdynamics of multidimensional shifts of finite type
- An order on sets of tilings corresponding to an order on languages
Cited In (42)
- Ergodic optimization in dynamical systems
- Arithmetical hierarchy of the Besicovitch-stability of noisy tilings
- Subsystem entropies of shifts of finite type and sofic shifts on countable amenable groups
- 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 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
- Zero-temperature chaos in bidimensional models with finite-range potentials
- Algorithmic complexity for the realization of an effective subshift by a sofic
- On the dynamics and recursive properties of multidimensional symbolic systems
- A generalization of the simulation theorem for semidirect products
- Projective subdynamics and universal shifts
- Automatic winning shifts
- The group of reversible Turing machines
- Title not available (Why is that?)
- Computability of topological entropy: from general systems to transformations on Cantor sets and the interval
- Hardness of conjugacy, embedding and factorization of multidimensional subshifts
- Seas of squares with sizes from a \(\Pi_{1}^{0}\) set
- Zero-temperature phase diagram for double-well type potentials in the summable variation class
- A notion of effectiveness for subshifts on finitely generated groups
- 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)
