complexity function of ultimately periodic words

65 Views Asked by At

Why do ultimately periodic words have a bounded complexity function? It's clear intuitively but I don't know how to formalize it

1

There are 1 best solutions below

0
On BEST ANSWER

Let $p_u(n)=\text{number of distinct $n$ substrings of $u$}.$ If $u$ is ultimately periodic it means that $u=wv^{\infty},$ where $v^{\infty}$ just means $vvvvvv\cdots $ so $$p_u(n)=p_{wv^{\infty}}(n)\leq p_{wv}(n)+p_{v^{\infty}}(n),$$ but $p_{wv}(n)\leq |wv|$ and $p_{v^{\infty}}(n)=p_{v^n}(n) \leq |v|$ cause $v^n$ is a periodic word.