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.

We introduce the two-dimensional rational automata (RA) to recognize languages of pictures, as an extension of the finite automata for strings. A RA processes a picture column by column changing its state. The states are columns of symbols, too. The transition function is realized by a transducer. We prove that RA recognize the family REC of languages recognized by tiling systems. Moreover, RA provide a uniform setting for a lot of important notions, techniques and results presented in the last decades for recognizable two-dimensional languages. The model is also very flexible. In fact, there can be imposed restrictions or added features to easily interesting new classes and examples or to capture known families of languages.

A setX⊆ Σ** of pictures is a code if every picture over Σ is tilable in at most one way with pictures inX. The definition ofstrong prefix codeis introduced. The family of finite strong prefix codes is decidable and it has a polynomial time decoding algorithm. Maximality for finite strong prefix codes is also studied and related to the notion of completeness. We prove that any finite strong prefix code can be embedded in a unique maximal strong prefix code that has minimal size and cardinality. A complete characterization of the structure of maximal finite strong prefix codes completes the paper.

Recognizable two-dimensional languages (REC) are defined by tiling systems that generalize to two dimensions non-deterministic finite automata for strings. We introduce the notion of deterministic tiling system and the corresponding family of languages (DREC) and study its structural and closure properties. Furthermore we show that, in contrast with the one-dimensional case, there exist other classes between deterministic and non-deterministic families that we separate by means of examples and decidability properties.