Semi-palindromes in g_98& some 
forbidden factors

© 2003 V. Keränen

You may copy the image words of  g85  and  g98  as text from here


Some structures in  g
98

g98a =  a   b   c   a   c   d   c   b   c   d   c   a   d   b   d   c   b   d   b   a  ...   b   c   b   a c   b   c   d   c   a   c   d   c   b   d   c   d   a   d   b   d   c   b   c   a

The underlined factors are semi-palindromes.
The longest of them (factor55 - explained below) is of length = 55.

g98a = "abc acdcbcdca db dcbdbabcbdc acbabdbabca bda
dcdadbdcbdbabdbcbacbcdbabdc d bdcacdbcbacbcdcacdcbdcdadbd cbca"

factor55 = w d (mir(w) /. {b ↔ c})

 d                    c                    d                    a                    d ... p;                 15                      

The structure of  factor55  is easier to see from here:

      d        c                    d                    a    ... p;     3                          2                          1

formalSum[factor55]

8 a + 15 b + 15 c + 17 d

g98  and  g85  compared:

g98a =  a   b   c   a   c   d   c   b   c   d   c   a   d   b   d   c   b   d   b   a  ...   b   c   b   a c   b   c   d   c   a   c   d   c   b   d   c   d   a   d   b   d   c   b   c   a

g85a = abcacdcbcdcadcdbdaba c     a     bad   b     a     bc    b     d     b     c    ...                 d                   c                   b                   c                   a

 pref_13(g_98) = pref_13(g_85)   &    suff_30(g_9 ...              d             b             d             c             b             c             a

Trying to construct a-2-free strings over  4  letters in some other way

A trial: every second letter is the same 5 times in succession

 abacadacabcbdbcbabdabacabadacdcbcdcacbacadabadacdbabdbcbdbadacabacadcbcdadbdcdbd"

You cannot continue this string of length 80.  (ok with  aba  but that's all)

Another example:  Use  {a,c}  in odd places and  {b,d}  in even places. How long can you continue?

Answer. This string is the longest possible:

 abadabcbadabadcdadcb<br /> cdcbabcbadabadcdabada

The same string in a readily comprehensible form:

 abadabcbadabadcdadcbcdcbabcbadabadcdabada

You cannot continue this string either!  Add any letter from {a,b,c,d} and it always creates an abelian square.

So there are long (safe-looking) a-2-free strings that are forbidden as factors in still longer a-2-free strings over  4  letters!

How did we find these examples?

More details:


Created by Mathematica  (November 2, 2003)