Algebraic and model-theoretic properties of tilings

[25] Algebraic and model-theoretic properties of tilings, Theoretical Computer Science 319 (2004), 103-126.
[28] Paperfolding sequences, paperfolding curves and local isomorphism, 39 pages (see pdf).
[29] Tilings and associated relational structures, 36 pages (see pdf).

In [25] and [29], we investigate the relations between the geometric properties of tilings and the algebraic and model-theoretic properties of associated relational structures. A tiling is a covering of a metric space, constructed from a finite number of prototiles, with a finite number of possible configurations for the immediate neighbours of a tile. Our study is motivated by the existence of aperiodic tilings, i.e. tilings, such as those constructed by Penrose or Robinson, obtained from sets of prototiles and configurations which give no periodic tiling.
The relational structure associated to a tiling is uniformly locally finite. We say that two tilings are
locally isomorphic if each bounded fragment of one of them is isomorphic to a fragment of the other one. We say that a tiling satisfies the local isomorphism property if it contains a copy of each of its bounded fragments in the neighbourhood of each of its points. Penrose tilings (respectively Robinson tilings) satisfy the local isomorphism property. There are continuously many such tilings, and all of them are locally isomorphic. Other similar examples exist, for euclidean or non euclidean spaces.

In [25], we consider tilings of euclidean spaces of finite dimension, and isomorphism is defined up to translation. We show that two tilings are locally isomorphic if and only if the associated relational structures are elementarily equivalent. In particular, the structures associated to two Penrose tilings (respectively two Robinson tilings) are elementarily equivalent. We generalize classical results concerning the local isomorphism property and the ''extraction preorder'' to larger classes of tilings, and more generally classes of uniformly locally finite relational structures. Also we give necessary and sufficient conditions for a relational structure to be representable by a tiling associated to some given set of prototiles and configurations.

In [29], we generalize the results of [25] by considering tilings of a metric space. Isomorphism is defined modulo a group of isometries of the space. Then we show that notions of periodicity and invariance through a translation, defined for tilings of the euclidean spaces R^k, can be generalized, with appropriate hypotheses, to relational structures, and in particular to tilings of non-euclidean spaces.
In the last part of [29], we investigate the properties of relational structures which are elementarily equivalent to rigid structures, i.e. structures without non-trivial automorphism. We obtain a characterization in the case of uniformly locally finite structures which satisfy the local isomorphism property. We give several examples, some of them obtained by considering relational structures associated to tilings of euclidean or non-euclidean spaces.

For each integer n, the n-folding sequences and the n-folding curves are obtained by folding n times a strip of paper in two, with each folding being done independently up or down, and unfolding it partially. In [28], we introduce complete folding sequences (resp. complete folding curves), which are sequences indexed by Z (resp. continuous functions from R to RxR) obtained as direct limits of n-folding sequences (resp. n-folding curves) for nЄN. We show that complete folding sequences satisfy local properties analogous to those of aperiodic tilings. Then we prove that each complete folding curve can be completed into a “covering” of the plane by complete folding curves which satisfies the local isomorphism property. We show that this covering is essentially unique, and contains at most six curves.