Periodicity in tilings

Abstract

Tilings and tiling systems are an abstract concept that arise both as a computational model and as a dynamical system. In this paper, we characterize the sets of periods that a tiling system can produce. We prove that up to a slight recoding, they correspond exactly to languages in the complexity classes $\nspace{n}$ and $\cne$.

References in corpus (2)

• An Order on Sets of Tilings Corresponding to an Order on Languages
• Growth-type invariants for ${\mathbb{Z}}^d$ subshifts of finite type and classes arithmetical of real numbers