Pattern Complexity of Aperiodic Substitutive Subshifts

05/03/2021
by   Etienne Moutot, et al.
0

This paper aims to better understand the link better understand the links between aperiodicity in subshifts and pattern complexity. Our main contribution deals with substitutive subshifts, an equivalent to substitutive tilings in the context of symbolic dynamics. For a class of substitutive subshifts, we prove a quadratic lower bound on their pattern complexity. Together with an already known upper bound, this shows that this class of substitutive subshifts has a pattern complexity in Θ(n^2). We also prove that the recent bound of Kari and Moutot, showing that any aperiodic subshift has pattern complexity at least mn+1, is optimal for fixed m and n.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset