Logo image
Sign in
A Combinatorial Proof of S-adicity for Sequences with Linear Complexity
Journal article   Peer reviewed

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

Julien Leroy and Gwenaël Richomme
Integers : Electronic Journal of Combinatorial Number Theory, Vol.13
25/01/2013

Abstract

subword complexity uniform recurrence factor complexity S-adicity linear complexity morphism S-adic conjecture
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.
url
Find in HALView

Metrics

1 Record Views

Details

Logo image