Lie complexity of words

DOI10.1016/J.TCS.2022.06.001MaRDI QIDQ6360055arXivFDO

Authors Jason P. Bell, Jeffrey Shallit

Publication date 7 February 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.TCS.2022.06.001

Mathematics Subject Classification ID

Automata sequences (11B85) Combinatorics on words (68R15)

arXiv classification

cs.DMcs.FLmath.CO

Abstract: Given a finite alphabet $Sigma$ and a right-infinite word $$ over $Sigma$, we define the Lie complexity function $$, whose value at $n$ is the number of conjugacy classes (under cyclic shift) of length-$n$ factors $x$ of $$ with the property that every element of the conjugacy class appears in $$. 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.

This page was built for publication: Lie complexity of words

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