mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, a locally catenative sequence is a sequence of

words A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no consen ...

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'': :

w(n)=w(n-i_1)w(n-i_2)\ldots w(n-i_k) \text n \ge \max\ \, .

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

Examples

The sequence of

Fibonacci word A Fibonacci word is a specific sequence of binary digits (or symbols from any two-letter alphabet). The Fibonacci word is formed by repeated concatenation in the same way that the Fibonacci numbers are formed by repeated addition. It is a parad ...

s ''S''(''n'') is locally catenative because :

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

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

References

Formal languages Combinatorics on words