Complexity of cutting words on regular tilings

We show that the complexity of a cutting word u in a regular tiling with a polyomino Q is equal to P-n (u) = (p + q - 1)n + I for all n >= 0, where P-n (u) counts the number of distinct factors of length n in the infinite word u and where the boundary of Q is constructed of 2p horizontal and 2q vertical unit segments. (c) 2006 Published by Elsevier Ltd.