Namespaces
Variants
Actions

Prototile

From Encyclopedia of Mathematics
Revision as of 16:55, 11 February 2012 by Peter Schmitt (talk | contribs) (new)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Template:Tiling/def

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$ such that all its tiles $T_i$ are congruent to some $P_k$.

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://encyclopediaofmath.org/index.php?title=Prototile&oldid=20982