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)$.
Type de document :
Communication dans un congrès
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), Aug 2017, Aalborg, Denmark. 83, pp.5:1-5:14, 2017, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). 〈http://drops.dagstuhl.de/portals/extern/index.php?semnr=16053〉. 〈10.4230/LIPIcs.MFCS.2017.5〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01623207
Contributeur : Andrei Romashchenko <>
Soumis le : mercredi 25 octobre 2017 - 10:41:24
Dernière modification le : mardi 11 septembre 2018 - 14:54:01

Lien texte intégral

Identifiants

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. 83, pp.5:1-5:14, 2017, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). 〈http://drops.dagstuhl.de/portals/extern/index.php?semnr=16053〉. 〈10.4230/LIPIcs.MFCS.2017.5〉. 〈lirmm-01623207〉

Partager

Métriques

Consultations de la notice

132