On the expressive power of quasiperiodic SFT

DOI10.4230/LIPICS.MFCS.2017.5MaRDI QIDQ5111219zbMATH OpenOpenAlexFDO

Authors Andrei Romashchenko, Bruno Durand

Publication date 26 May 2020

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

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)

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)$.

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

Cites work

• Complex tilings
• Fixed-point tile sets and their applications
• Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences
• On the dynamics and recursive properties of multidimensional symbolic systems
• On uniform recurrence of a direct product
• Quasiperiodicity and non-computability in tilings
• Reliable computation with cellular automata
• Simulation of effective subshifts by two-dimensional subshifts of finite type
• Symbolic Dynamics
• Tilings and quasiperiodicity.
• Tilings robust to errors
• Turing degree spectra of minimal subshifts
• Turing degrees of multidimensional SFTs

Cited in

(11)

• The expressiveness of quasiperiodic and minimal shifts of finite type
• A characterization of the sets of periods within 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
• Algorithmic complexity for the realization of an effective subshift by a sofic
• Projective subdynamics and universal shifts
• scientific article; zbMATH DE number 7559149 (Why is no real title available?)
• Seas of squares with sizes from a \(\Pi_{1}^{0}\) set
• Decidability and universality of quasiminimal subshifts
• 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)