6533b831fe1ef96bd1298f83
RESEARCH PRODUCT
On the Lie complexity of Sturmian words
Gabriele FiciAlessandro De Lucasubject
FOS: Computer and information sciencesGeneral Computer ScienceSettore INF/01 - InformaticaDiscrete Mathematics (cs.DM)Formal Languages and Automata Theory (cs.FL)Sturmian wordComputer Science - Formal Languages and Automata TheoryComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)G.2.168R15Lie complexityTheoretical Computer ScienceLie complexity Sturmian wordFOS: MathematicsMathematics - CombinatoricsCombinatorics (math.CO)Computer Science::Formal Languages and Automata TheoryComputer Science - Discrete Mathematicsdescription
Bell and Shallit recently introduced the Lie complexity of an infinite word $s$ as the function counting for each length the number of conjugacy classes of words whose elements are all factors of $s$. They proved, using algebraic techniques, that the Lie complexity is bounded above by the first difference of the factor complexity plus one; hence, it is uniformly bounded for words with linear factor complexity, and, in particular, it is at most 2 for Sturmian words, which are precisely the words with factor complexity $n+1$ for every $n$. In this note, we provide an elementary combinatorial proof of the result of Bell and Shallit and give an exact formula for the Lie complexity of any Sturmian word.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2022-01-01 |