The S-adic conjecture on sub-linear complexity
The S-adic conjecture on sub-linear complexity
Let be a sequence over a finite alphabet. An -adic sequence is one admitting an -adic representation for some set of morphisms; in particular, the representation is given by morphisms and letters , with and lengths tending to infinity. The factor complexity of a sequence is the function counting its distinct factors of each length. -adic conjecture. There exists a condition such that a sequence has sub-linear complexity if and only if it is an -adic sequence satisfying condition for some finite set of morphisms. This is posed as an open problem concerning the relationship between low factor complexity and finite-set -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.