Characterizations of periods of multi-dimensional shifts
Emmanuel Jeandel, Pascal Vanier · Ergodic Theory and Dynamical Systems · 2013
Abstract We show that the sets of periods of multi-dimensional shifts of finite type are precisely the sets of integers of the complexity classNP. We also show that the functions counting their number are the functions of #P. We also give characterizations of some other notions of periodicity in terms of space complexity. We finish the paper by giving some characterizations for sofic and effective subshifts.