A Combinatorial Proof of S-adicity for Sequences with Linear Complexity

Julien Leroy 1 Gwenaël Richomme 2, 3, 4
1 LAMFA - Laboratoire Amiénois de Mathématique Fondamentale et Appliquée
2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 UM3 - Université Paul-Valéry - Montpellier 3
4 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Using Rauzy graphs, Ferenczi proved that if a symbolic dynamical system has linear complexity then it is S-adic. Being more specific, the result can also be proved for infinite words. We provide a new proof of this latter result using the notion of return words to a set of words.
Keywords : factor complexity uniform recurrence linear complexity morphism subword complexity S-adic conjecture S-adicity
Type de document :
Article dans une revue
Integers : Electronic Journal of Combinatorial Number Theory, State University of West Georgia, Charles University, and DIMATIA, 2013, 13, pp.article #A5. 〈http://www.integers-ejcnt.org/vol13.html〉
Liste complète des métadonnées
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00797658
Contributeur : Gwenaël Richomme <>
Soumis le : jeudi 7 mars 2013 - 08:36:01
Dernière modification le : jeudi 11 janvier 2018 - 06:27:05

Identifiants

  • HAL Id : lirmm-00797658, version 1

Collections

INSMI | ARITH | LIRMM | ESCAPE | TDS-MACS | MIPS | UNIV-MONTPELLIER

Citation

Julien Leroy, Gwenaël Richomme. A Combinatorial Proof of S-adicity for Sequences with Linear Complexity. Integers : Electronic Journal of Combinatorial Number Theory, State University of West Georgia, Charles University, and DIMATIA, 2013, 13, pp.article #A5. 〈http://www.integers-ejcnt.org/vol13.html〉. 〈lirmm-00797658〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

141

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD