Lie complexity of words.

Given a finite alphabet Σ and a right-infinite word w over Σ, we define the Lie complexity function L w : N → N , 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. 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 also k -automatic. [ABSTRACT FROM AUTHOR]