On the expressive power of quasiperiodic SFT

Andrei Romashchenko 1 Bruno Durand 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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 $n\times n$ is $\Omega(n)$.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01623207
Contributor : Andrei Romashchenko <>
Submitted on : Wednesday, October 25, 2017 - 10:41:24 AM
Last modification on : Tuesday, September 11, 2018 - 2:54:01 PM

Links full text

Identifiers

Citation

Andrei Romashchenko, Bruno Durand. On the expressive power of quasiperiodic SFT. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), Aug 2017, Aalborg, Denmark. pp.5:1-5:14, ⟨10.4230/LIPIcs.MFCS.2017.5⟩. ⟨lirmm-01623207⟩

Share

Metrics

Record views

160