From: Ian Wanless
Subject: Re: Strings not containing two identical consecutive substrings
Date: Fri, 5 Nov 1999 11:05:55 +0000
Newsgroups: sci.math.research
Keywords: square-free words
On Thu, 4 Nov 1999, Mohammad Mahdian wrote:
> Prove (or disprove) that for every n, there is a string of 1, 2, 3 of
> length n which does not contain two consecutive substring which are
> equal. For example 11, 32121, and 121321312 are not acceptable, but
> 121312313 is acceptable.
Yes there are arbitrarily long such strings (called square-free words).
This is a classical result, due originally I think to
A. Thue [Christiania Vidensk. Selsk. Skv. 1912, no. 1; Jbuch 43, 162]
Indeed, Franz-Josef Brandenburg, shows there are exponentially many such
words in: [Uniformly growing k-th power-free homomorphisms.
Theoret. Comput. Sci. 23 (1983), no. 1, 69--82]
One example is to found by starting with the word "1" and then repeatedly
applying the replacements
1 -> 123
2 -> 13
3 -> 2
So you get words
123
123132
123132123213
123132123213123132131232
123132123213123132131232123132123213123212313213
etc
All of which, if I've remembered the construction right, will be
square-free (and each is an initial segment of the next).
On Thu, 4 Nov 1999, Chris Simmons wrote:
> This is false. You encounter this
> construction in semigroup theory in the free band.
We must be talking about different things.
-i
-----------------------------------------------------------
Ian Wanless Christ Church
ph: +44 1865 276124 St Aldates
e-m: wanless@maths.ox.ac.uk Oxford OX1 1DP UK
-----------------------------------------------------------
==============================================================================
From: ilya@math.ohio-state.edu (Ilya Zakharevich)
Subject: Re: Strings not containing two identical consecutive substrings
Date: 7 Nov 1999 18:30:21 -0600
Newsgroups: sci.math.research
[A complimentary Cc of this posting was sent to Chris Simmons
],
who wrote in article :
> Whoops, sorry, I failed to appreciate that a word which in itself contains
> no squares can reduce (in the free band) to a shorter word non the less.
IIRC, the result (Martin-Löf?) is that any infinite word in any finite
alphabet contains a subsequence ABABA with nonempty subwords A and B.
It is relatively easy to construct a word without AAA: take the
grammar
0 -> 001
1 -> 110
and apply it to 0.
Ilya
==============================================================================
From: Mark Sapir
Subject: Re: Strings not containing two identical consecutive substrings
Date: 8 Nov 1999 10:30:02 -0600
Newsgroups: sci.math.research
Ilya Zakharevich wrote:
[previous article was quoted --djr]
>IIRC, the result (Martin-Löf?) is that any infinite word in any finite
>alphabet contains a subsequence ABABA with nonempty subwords A and B.
This is wrong, for example, because ABABA contains ABAB which is a
square , and there are infinite sequences in 3 letters which are
square-free (see Thue or Arshon or Morse-Hedlund or hundreds of other
papers on the subject of avoidable words).
>
> It is relatively easy to construct a word without AAA: take the
> grammar
>
> 0 -> 001
> 1 -> 110
>
> and apply it to 0.
>
The Tue-Arshon-Morse-Hedlund substitution is 0-->01, 1-->10.
Mark
==============================================================================
["Arshon" may be a typo; there are no article with author=Arshon in MathSciNet
--djr]