EVENT DETAILS AND ABSTRACT

Title: Words with complexity constraints
Speaker: Julien Cassaigne
Speaker Info: CNRS
Brief Description:
Special Note: note unusual day
Abstract:

The complexity function p(n) of an infinite word (or of a subshift) counts the number of finite words of each length that occur in it. Certain constraints on p(n) imply dynamical properties of the subshift, e.g. p(n) \leq for some n implies periodicity (Morse and Hedlund), or limsup p(n)/n < 3 implies unique ergodicity (Boshernitzan). Here we are mainly interested in constraints on \liminf p(n)/n and \limsup p(n)/n. We discuss how Rauzy graphs and substitutions may be used to give explicit descriptions of families of words satisfying such constraints, or to prove that they cannot be satisfied.