Towards a statement of the S-adic conjecture through examples

2012/08/31 by Fabien Durand, Durand, Fabien, Julien Leroy +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Dynamics and Fractals #cs.DM #math.CO #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1208.6376

25

arxiv created 2012/08/31 · openalex publication_date 2012/08/31 · arxiv updated 2012/09/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The S-adic conjecture claims that there exists a condition C such that a sequence has a sub-linear complexity if and only if it is an S-adic sequence satisfying Condition 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 counter-examples to what could be believed to be "a good Condition C".

Citations

• Symbolic Dynamics II. Sturmian Trajectories

Related

• An S-adic characterization of minimal subshifts with first difference of complexity 1 ≤ p(n+1) - p(n) ≤ 2
• The structure of low complexity subshifts
• On the Nth 2-adic complexity of binary sequences identified with algebraic 2-adic integers
• On the automorphism group of minimal S-adic subshifts of finite alphabet rank
• On the Factor Complexity Associated with a Family of Multidimensional Continued Fraction Algorithms