# Prototile

$ \def\T{\mathcal T} % tiling \def\P{\mathcal P} % protoset $

In the theory of tilings a **set of prototiles**, also called a **protoset**,
is a (finite or infinite) set of tiles that represent (by congruence) all the tiles of a tiling, or of a class of tilings.

A protoset $ \P = \{P_k\} $ *admits* a tiling if there is a tiling $ \T = \{T_i\} $ such
that all its tiles $T_i$ are congruent to some $P_k$.

An *$n$-hedral* tiling is a tiling in that $n$ (distinct) prototiles occur.
For $n=1,2,3,...$ the terms *monohedral*, *dihedral*, *trihedral*, etc. are used.

#### Tiling problem

The tiling problem, i.e., the problem to determine whether a protoset admits a tiling is (algorithmically) undecidable,
both in general and for many special cases.
Normally, a protoset will (if at all) admit either a single tiling or uncountably many tilings, but intermediate numbers are also possible.
If a protoset admits (up to congruence) only a single tiling then it is called *monomorphic*,
if it admits precisely two distinct tilings it called *dimorphic*, *trimorphic* for three tilings, etc.,
$n$-morphic for $n$ tilings, and $\sigma$-morphic if there are countably many distinct tilings.

**How to Cite This Entry:**

Prototile.

*Encyclopedia of Mathematics.*URL: http://www.encyclopediaofmath.org/index.php?title=Prototile&oldid=30989