Finite-state transducers for substitution tilings
Simon Tatham · 2025
Read Finite-state transducers for substitution tilings by Simon Tatham (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-16595.txt.
Introduction
Simon Tatham presents algorithms for patterned tilings in their 53-page 2025 arXiv paper. Substitution tilings grow by inflating and subdividing shapes again and again. They produce famous patterns like Penrose tiles, hats, and Spectres. Managing the nested hierarchy of supertiles by hand is fiddly and error-prone.
Tatham treats a tile's ancestry in purely combinatorial terms. Finite-state automata do the bookkeeping. The resulting toolkit generates patches of tilings with ease. It makes both random samples and deliberately chosen arrangements. It also supports some analyses of the tiling itself. A notable product is two substitution systems for the hat tiling. Both are unambiguous: a single tile's address determines the rest of the plane. The paper is a practical gift to programmers and mathematicians who build or study aperiodic tilings.
Catalog record
| CREATOR | Simon Tatham |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 157 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-16595