Tiling of toroidal arrays with pictures: Uniqueness, shift-equivalence and undecidability

A toroidal array is a two-dimensional (2D) array of symbols in a finite alphabet where opposite sides are coincident. Alternatively, it can be figured out as a picture wrapped around a torus. Toroidal codes are finite sets of pictures which can tile any toroidal array in at most one unique way. They are the 2D counterpart of circular codes of strings. On the other hand, shift-invariant toroidal codes of pictures form a larger family of codes; here, two tilings of the same toroidal array are viewed as a single tiling when one is obtained by a shift of the other one. We prove that it is undecidable whether a finite set of pictures is a toroidal or a shift-invariant toroidal code. The problem becomes polynomially decidable for sets of cardinality one, using a combinatorial characterization of such sets. In analogy to the string case, toroidal and shift-invariant toroidal codes are investigated referring to conjugate, self-conjugate and self-covering pictures.