Locally catenative sequence

In mathematics, a locally catenative sequence is a sequence of words in which each word can be constructed as the concatenation of previous words in the sequence.¹

Formally, an infinite sequence of words w(n) is locally catenative if, for some positive integers k and i₁,...i_k:

${\displaystyle w(n)=w(n-i_{1})w(n-i_{2})\ldots w(n-i_{k}){\text{ for }}n\geq \max\{i_{1},\ldots ,i_{k}\}\,.}$

Some authors use a slightly different definition in which encodings of previous words are allowed in the concatenation.²

The sequence of Fibonacci words S(n) is locally catenative because

${\displaystyle S(n)=S(n-1)S(n-2){\text{ for }}n\geq 2\,.}$

The sequence of Thue–Morse words T(n) is not locally catenative by the first definition. However, it is locally catenative by the second definition because

${\displaystyle T(n)=T(n-1)\mu (T(n-1)){\text{ for }}n\geq 1\,,}$

where the encoding μ replaces 0 with 1 and 1 with 0.