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

CREATORSimon Tatham
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE157 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-16595

Browse the full library · About the Tower of Babel