Locally catenative sequence explained

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.^[1]

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

w(n) = w(n - i _{1)w(n-i} _{2)\ldots} w(n - i _{k)} for n \ge max \{i _{1,} \ldots, i _{k\}} .

Some authors use a slightly different definition in which encodings of previous words are allowed in the concatenation.^[2]

Examples

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

S(n) = S(n -1 )S(n -2 ) for n \ge 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

T(n) = T(n -1 )\mu(T(n -1 )) for n \ge 1 , where the encoding μ replaces 0 with 1 and 1 with 0.

References

1. Book: Rozenberg , Grzegorz . Salomaa, Arto . Handbook of Formal Languages . Springer . 1997 . 262 . 3-540-60420-0.
2. Book: Allouche , Jean-Paul . Shallit, Jeffrey . Automatic Sequences . Cambridge . 2003 . 237 . 0-521-82332-3.