Lie complexity of words
share
Given a finite alphabet Σ and a right-infinite word w over Σ, we define the Lie complexity function L_ w:ℕ→ℕ, whose value at n is the number of conjugacy classes (under cyclic shift) of length-n factors x of w with the property that every element of the conjugacy class appears in w. We show that the Lie complexity function is uniformly bounded for words with linear factor complexity, and as a result we show that words of linear factor complexity have at most finitely many primitive factors y with the property that y^n is again a factor for every n. We then look at automatic sequences and show that the Lie complexity function of a k-automatic sequence is again k-automatic.
READ FULL TEXT