On the Lie complexity of Sturmian words

DOI10.1016/J.TCS.2022.10.009arXiv2206.00995MaRDI QIDQ6400908FDOQ6400908

Authors: Alessandro De Luca, Gabriele Fici 

Publication date: 2 June 2022

Abstract: 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.

Mathematics Subject Classification ID

Combinatorics on words (68R15)

This page was built for publication: On the Lie complexity of Sturmian words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6400908)