Sesquipower

In mathematics, a sesquipower or Zimin word is a string over an alphabet with identical prefix and suffix. Sesquipowers are unavoidable patterns, in the sense that all sufficiently long strings contain one.

Formal definition

Formally, let A be an alphabet and A be the free monoid of finite strings over A. Every non-empty word w in A+ is a sesquipower of order 1. If u is a sequipower of order n then any word w = uvu is a sesquipower of order n + 1.[1] The degree of a non-empty word w is the largest integer d such that w is a sesquipower of order d.[2]

Bi-ideal sequence

A bi-ideal sequence is a sequence of words fi where f1 is in A+ and

f_{i+1} = f_i g_i f_i \

for some gi in A and i  1. The degree of a word w is thus the length of the longest bi-ideal sequence ending in w.[2]

Unavoidable patterns

For a finite alphabet A on k letters, there is an integer M depending on k and n, such that any word of length M has a factor which is a sesquipower of order at least n. We express this by saying that the sesquipowers are unavoidable patterns.[3][4]

Sesquipowers in infinite sequences

Given an infinite bi-ideal sequence, we note that each fi is a prefix of fi+1 and so the fi converge to an infinite sequence

 f = f_1 g_1 f_1 g_2 f_1 g_1 f_1 g_3 f_1 \cdots \

We define an infinite word to be a sesquipower if is the limit of an infinite bi-ideal sequence.[5] An infinite word is a sesquipower if and only if it is a recurrent word,[5][6] that is, every factor occurs infinitely often.[7]

Fix a finite alphabet A and assume a total order on the letters. For given integers p and n, every sufficiently long word in A has either a factor which is a p-power or a factor which is an n-sesquipower; in the latter case the factor has an n-factorisation into Lyndon words.[6]

References

  1. Lothaire (2011) p. 135
  2. 1 2 Lothaire (2011) p. 136
  3. Lothaire (2011) p. 137
  4. Berstel et al (2009) p.132
  5. 1 2 Lothiare (2011) p. 141
  6. 1 2 Berstel et al (2009) p.133
  7. Lothaire (2011) p. 30
This article is issued from Wikipedia - version of the Wednesday, November 26, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.