Locally catenative sequence: Difference between revisions

Revision as of 09:01, 7 June 2009

Latest revision as of 08:21, 21 July 2022

(5 intermediate revisions by 4 users not shown)

Line 1:

In [[mathematics]], a '''locally catenative sequence''' is a sequence of [[word (mathematicsformal language theory)|words]] in which each word can be constructed as the concatenation of previous words in the sequence.<ref>{{cite book

| last = Rozenberg

| first = Grzegorz

| coauthors author2= Salomaa, Arto

| title = Handbook of Formal Languages

| publisher = Springer

| date = 1997

| pages = 262

| isbn = 35406042003-540-60420-0}}</ref>

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

:<math>w(n)=w(n-i_1)w(n-i_2)...\ldots w(n-i_k) \text{ for } n \ge \max(\{i_1, ...\ldots, i_k)\} \, .</math>

Some authors use a slightly different definition in which encodings of previous words are allowed in the concatenation.<ref>{{cite book

| last = Allouche

| first = Jean-Paul

| coauthors author2= Shallit, Jeffrey

| title = Automatic Sequences

| publisher = Cambridge

| date = 2003

Line 26:

:<math>S(n)=S(n-1)S(n-2) \text{ for } n \ge 2 \, .</math>

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

:<math>T(n)=T(n-1)\mu(T(n-1)) \text{ for } n \ge 1 \, ,</math>

where the encoding ''&mu;'' replaces 0 with 1 and 1 with &nbsp;0.

==References==