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]