The S-adic conjecture on sub-linear complexity

Let f53ff53f be a sequence over a finite alphabet. An SS-adic sequence is one admitting an SS-adic representation for some set SS of morphisms; in particular, the representation is given by morphisms f70fn:An+1Anf70f_n:A_{n+1}^*\to A_n^* and letters anAna_n\in A_n, with f53f=limn+f70f0f70f1\cdotsf70fn(an+1ω)f53f=\lim_{n\to+\infty}f70f_0f70f_1\cdotsf70f_n(a_{n+1}^{\omega}) and lengths tending to infinity. The factor complexity of a sequence is the function counting its distinct factors of each length. SS-adic conjecture. There exists a condition CC such that a sequence has sub-linear complexity if and only if it is an SS-adic sequence satisfying condition CC for some finite set SS of morphisms. This is posed as an open problem concerning the relationship between low factor complexity and finite-set SS-adic representations; the source gives no resolution.

Sources & referencesView supporting material

Primary source

Fabien Durand, Julien Leroy and Gwénaël Richomme, “Towards a statement of the S-adic conjecture through examples”, arXiv:1208.6376 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.