second commit

1 files changed, 94 insertions, 0 deletions

diff --git a/posts/2015-05-30-infinite-binary-words-containing-repetitions-odd-periods.md b/posts/2015-05-30-infinite-binary-words-containing-repetitions-odd-periods.md
new file mode 100644
index 0000000..8f2ff8e
--- /dev/null
+++ b/posts/2015-05-30-infinite-binary-words-containing-repetitions-odd-periods.md
@@ -0,0 +1,94 @@
+---
+template: oldpost
+title: AMS review of 'Infinite binary words containing repetitions of odd period' by Badkobeh and Crochemore
+date: 2015-05-30
+comments: true
+archive: false
+---
+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;
+[MR2142071](http://www.ams.org/mathscinet/search/publdoc.html?r=1&pg1=MR&s1=2142071&loc=fromrevtext)\].
+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.