Kolloquiumsvortrag: Prof. Dr. James Currie / 17.04.2015
17.04.2015 von 14:15 bis 15:45
Institut für Informatik, Ludewig-Meyn-Str. 2, Übungsraum 2
Titel: Growth rate of binary words avoiding xxxR
Abstract:Consider the set of those binary words with no non-empty factors of the form xxxR. Du, Mousavi, Schaeffer, and Shallit asked whether this set of words grows polynomially or exponentially with length. In this talk, we demonstrate the existence of upper and lower bounds on the number of such words of length n, where each of these bounds is asymptotically equivalent to a (different) function of the form Cnlg n+c, where C, c are constants.