🚀 go-pugleaf

DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

THEORY SEMINAR

                    -May 26, 1989

Dr.  Robert Cori, University of Bordeaux, will speak on
"Partially abelian square free words."

TIME:                 11:30 a.m.

ROOM:              DC 1304

ABSTRACT

     The   notions   of   square-freeness  and  abelian
square-freeness  of  words  are  well known examples of
avoidable  properties  of  words  on sufficiently large
alphabets.
     It  is  known  since  the beginning of the century
that   square-free   words   exist   on   alphabets  of
cardinality greater than 3, and answering to a question
of  Erdos, Pleasants has shown in 1968 the existence of
abelian square free words of arbitrary length in a five
letter  alphabet.   The  existence of such words on a 4
letter alphabet is still an open question.
     The   recent   interest  of  theoretical  computer
scientists   for  partially  commutative  free  monoids
suggests  the  introduction  of the notion of partially
abelian squares which generalizes these two notions.
     One  of  the  main  results  obtained concerns the
existence  concerns  the  existence  of  arbitrary long
partially  abelian  square  free  words  on  a 4 letter
alphabet,  when  4  among  the  6 possible commutations
hold.  Other  results, mainly on enumeration, are given
in  a  three  letter  alphabet. In such an alphabet the
number  of square free words of length n is known to be
greater  than  an  exponential of n , it turns out that
the number of partially abelian square free words (when
only  one  commutation holds) is bounded by a polynomia
in n of degree 2.