1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
#+title: AMS review of 'Infinite binary words containing repetitions of
#+title: odd period' by Badkobeh and Crochemore
#+date: <2015-05-30>
This paper is about the existence of pattern-avoiding infinite binary
words, where the patterns are squares, cubes and \(3^+\)-powers.
There are mainly two kinds of results, positive (existence of an
infinite binary word avoiding a certain pattern) and negative
(non-existence of such a word). Each positive result is proved by the
construction of a word with finitely many squares and cubes which are
listed explicitly. First a synchronising (also known as comma-free)
uniform morphism \(g\: \Sigma_3^* \to \Sigma_2^*\)
is constructed. Then an argument is given to show that the length of
squares in the code \(g(w)\) for a squarefree \(w\) is bounded, hence
all the squares can be obtained by examining all \(g(s)\) for \(s\) of
bounded lengths. The argument resembles that of the proof of, e.g.,
Theorem 1, Lemma 2, Theorem 3 and Lemma 4 in [N. Rampersad, J. O.
Shallit and M. Wang, Theoret. Comput. Sci. *339* (2005), no. 1, 19--34;
[[http://www.ams.org/mathscinet/search/publdoc.html?r=1&pg1=MR&s1=2142071&loc=fromrevtext][MR2142071]]].
The negative results are proved by traversing all possible finite words
satisfying the conditions.
Let \(L(n_2, n_3, S)\) be the maximum length of a word with \(n_2\)
distinct squares, \(n_3\) distinct cubes and that the periods of the
squares can take values only in \(S\) , where \(n_2, n_3 \in \Bbb N \cup
\{\infty, \omega\}\) and \(S \subset \Bbb N_+\) . \(n_k = 0\)
corresponds to \(k\)-free, \(n_k = \infty\) means no restriction on the
number of distinct \(k\)-powers, and \(n_k = \omega\) means
\(k^+\)-free.
Below is the summary of the positive and negative results:
1) (Negative) \(L(\infty, \omega, 2 \Bbb N) < \infty\) : \(\nexists\) an
infinite \(3^+\) -free binary word avoiding all squares of odd
periods. (Proposition 1)
2) (Negative) \(L(\infty, 0, 2 \Bbb N + 1) \le 23\) : \(\nexists\) an
infinite 3-free binary word, avoiding squares of even periods. The
longest one has length \(\le 23\) (Proposition 2).
3) (Positive) \(L(\infty, \omega, 2 \Bbb N +
1) - = \infty\) :: \(\exists\) an infinite \(3^+\) -free binary word
avoiding squares of even periods (Theorem 1).
4) (Positive) \(L(\infty, \omega, \{1, 3\}) = \infty\) : \(\exists\) an
infinite \(3^+\) -free binary word containing only squares of period
1 or 3 (Theorem 2).
5) (Negative) \(L(6, 1, 2 \Bbb N + 1) = 57\) : \(\nexists\) an infinite
binary word avoiding squares of even period containing \(< 7\)
squares and \(< 2\) cubes. The longest one containing 6 squares and 1
cube has length 57 (Proposition 6).
6) (Positive) \(L(7, 1, 2 \Bbb N + 1) = \infty\) : \(\exists\) an
infinite \(3^+\) -free binary word avoiding squares of even period
with 1 cube and 7 squares (Theorem 3).
7) (Positive) \(L(4, 2, 2 \Bbb N + 1) = \infty\) : \(\exists\) an
infinite \(3^+\) -free binary words avoiding squares of even period
and containing 2 cubes and 4 squares (Theorem 4).
Copyright notice: This review is published at
http://www.ams.org/mathscinet-getitem?mr=3313467, its copyright owned by
the AMS.
|
