**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.