An S-adic characterization of minimal subshifts with first difference of complexity 1 ≤ p(n+1) - p(n) ≤ 2

Abstract : An S-adic characterization of minimal subshifts with first difference of complexity 1 ≤ p(n + 1) − p(n) ≤ 2 S. Ferenczi proved that any minimal subshift with first difference of complexity bounded by 2 is S-adic with Card(S) ≤ 3 27. In this paper, we improve this result by giving an S-adic characterization of these subshifts with a set S of 5 morphisms, solving by this way the S-adic conjecture for this particular case.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (in progress) (1), pp.233-286
Liste complète des métadonnées

Littérature citée [39 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01179422
Contributeur : Hélène Lowinger <>
Soumis le : mercredi 22 juillet 2015 - 14:36:02
Dernière modification le : jeudi 7 septembre 2017 - 01:03:40
Document(s) archivé(s) le : vendredi 23 octobre 2015 - 11:11:46

Fichier

dmtcs-16-1-15.pdf
Accord explicite pour ce dépôt

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-01179422, version 1

Collections

Citation

Julien Leroy. An S-adic characterization of minimal subshifts with first difference of complexity 1 ≤ p(n+1) - p(n) ≤ 2. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (in progress) (1), pp.233-286. 〈hal-01179422〉

Partager

Métriques

Consultations de la notice

141

Téléchargements de fichiers

108