Institut de Mathématiques de Luminy

Abstract 2002-22

Hubert Pascal, Vuillon Laurent.
Complexity of cutting words on regular tilings.

We show that the complexity of a cutting word u in a regular tiling by a polyomino Q is equal to Pn(u) = (p+q-1)n+1,A(inverse)n > or = 0. Where Pn(u) counts the number of distinct factors of length n in the infinite word u and where the boundary of Q is constructed by 2p horizontal and 2q vertical unit segments.

Keywords: cutting words, regular tilings, complexity function, flow on the torus, combinatorics on words.


Last update : november 18, 2002, EL.