Skip to Main content Skip to Navigation
Journal articles

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

Julien Leroy 1 Gwenaël Richomme 2, 3 
1 LAMFA - Laboratoire Amiénois de Mathématique Fondamentale et Appliquée - UMR CNRS 7352
2 UPVM - Université Paul-Valéry - Montpellier 3
3 ESCAPE - Systèmes complexes, automates et pavages
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 : subword complexity uniform recurrence factor complexity S-adicity linear complexity morphism S-adic conjecture
Document type :
Journal articles
Complete list of metadata
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00797658
Contributor : Gwenaël Richomme Connect in order to contact the contributor
Submitted on : Thursday, March 7, 2013 - 8:36:01 AM
Last modification on : Friday, August 5, 2022 - 3:02:59 PM

Identifiers

  • HAL Id : lirmm-00797658, version 1

Collections

CNRS | UNIV-MONTP3 | INSMI | ESCAPE | LIRMM | TDS-MACS | MIPS | UNIV-MONTPELLIER | U-PICARDIE | LAMFA

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. ⟨lirmm-00797658⟩

Export

BibTeX TEI DC DCterms EndNote Datacite

Share

Metrics

Record views

136