Локально катенативная последовательность

В математике — локально катенативная последовательность это последовательность слов , в которой каждое слово может быть построено как конкатенация предыдущих слов в последовательности.

Формально бесконечная последовательность слов w ( n ) является локально цепной, если для некоторых натуральных чисел k и i ₁ ,... i _k :

$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}\}\,.$

Некоторые авторы используют несколько иное определение, согласно которому при конкатенации допускаются кодировки предыдущих слов.

Примеры

Последовательность слов Фибоначчи S ( n ) является локально катенативной, потому что

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

Последовательность слов Туэ–Морса T ( n ) не является локально цепной по первому определению. Однако по второму определению он является локально катенативным, поскольку

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

где кодировка µ заменяет 0 на 1 и 1 на 0.