Journal of Integer Sequences, Vol. 16 (2013), Article 13.2.6

Do the Properties of an S-adic Representation Determine Factor Complexity?


Fabien Durand
LAMFA, CNRS UMR 7352
Université de Picardie Jules Verne
UFR des Sciences
33, rue Saint-Leu
80039 Amiens Cedex 1
France

Julien Leroy
Department of Mathematics
University of Liège
Grande Traverse 12 (B37)
B-4000 Liège, Belgium
and
LAMFA, CNRS UMR 7352
Université de Picardie Jules Verne
UFR des Sciences
33, rue Saint-Leu
80039 Amiens Cedex 1
France

Gwenaël Richomme
Université Paul-Valéry Montpellier 3
UFR IV, Dpt MIAp, Case J11
Route de Mende
34199 Montpellier Cedex 5
France
and
LIRMM (CNRS, Univ. Montpellier 2) - UMR 5506 - CC 477
161 rue Ada
34095 Montpellier Cedex 5
France

Abstract:

The S-adic conjecture postulates the existence of a condition C such that a sequence has linear complexity if and only if it is an S-adic sequence satisfying C for some finite set S of morphisms. We present an overview of the factor complexity of S-adic sequences and we give some examples that either illustrate some interesting properties, or that are counterexamples to what might seem to be a "good" condition C.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequence A003849 A010060 A049320.)

Received June 23 2012; revised version received October 9 2012. Published in Journal of Integer Sequences, March 2 2013.

Return to Journal of Integer Sequences home page