On the expressive power of quasiperiodic SFT

DOI10.4230/LIPICS.MFCS.2017.5zbMATH Open1441.37021arXiv1705.01876OpenAlexW2962772901MaRDI QIDQ5111219FDOQ5111219

Bruno Durand, Andrei Romashchenko

Publication date: 26 May 2020

Abstract: In this paper we study the shifts, which are the shift-invariant and topologically closed sets of configurations over a finite alphabet in $mathbb{Z}^d$. The minimal shifts are those shifts in which all configurations contain exactly the same patterns. Two classes of shifts play a prominent role in symbolic dynamics, in language theory and in the theory of computability: the shifts of finite type (obtained by forbidding a finite number of finite patterns) and the effective shifts (obtained by forbidding a computably enumerable set of finite patterns). We prove that every effective minimal shift can be represented as a factor of a projective subdynamics on a minimal shift of finite type in a bigger (by $1$) dimension. This result transfers to the class of minimal shifts a theorem by M.Hochman known for the class of all effective shifts and thus answers an open question by E.Jeandel. We prove a similar result for quasiperiodic shifts and also show that there exists a quasiperiodic shift of finite type for which Kolmogorov complexity of all patterns of size $nimesn$ is $Omega(n)$.

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

Recommendations

• The expressiveness of quasiperiodic and minimal shifts of finite type
• Characterizations of periods of multi-dimensional shifts
• Simulation of effective subshifts by two-dimensional subshifts of finite type
• Multidimensional shifts of finite type and sofic shifts
• Perturbations of multidimensional shifts of finite type

zbMATH Keywords

tilingsquasiperiodicityminimal SFT

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Theory of numerations, effectively presented structures (03D45) Multidimensional shifts of finite type (37B51)

Cites Work

• On the dynamics and recursive properties of multidimensional symbolic systems
• Simulation of effective subshifts by two-dimensional subshifts of finite type
• Fixed-point tile sets and their applications
• Tilings and quasiperiodicity.
• Complex tilings
• Turing degrees of multidimensional SFTs
• Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences
• Reliable computation with cellular automata
• Symbolic Dynamics
• Title not available (Why is that?)
• Turing degree spectra of minimal subshifts
• Tilings Robust to Errors
• Quasiperiodicity and Non-computability in Tilings

Cited In (6)

• The expressiveness of quasiperiodic and minimal shifts of finite type
• Quantified block gluing for multidimensional subshifts of finite type: aperiodicity and entropy
• The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics
• Characterizing entropy dimensions of minimal mutidimensional subshifts of finite type
• Title not available (Why is that?)
• Simulation of effective subshifts by two-dimensional subshifts of finite type

This page was built for publication: On the expressive power of quasiperiodic SFT

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