New maths blog post! The fifth in my series about handling aperiodic tilings combinatorially with string-processing algorithms:
https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/aperiodic-refine/
In this instalment I've automated the process of converting a tiling substitution system into one for which you can build a deterministic transducer, if the starting system didn't already admit one. I discuss the algorithm, its limitations, and a particular success in which it found a more economical substitution system for the hat tiling than any I already knew of.
A patch of the Ammann-Beenker tiling, consisting of squares and 45° rhombuses placed so as to satisfy some constraints (not shown) on which edges can meet. This particular patch has the symmetry group of a regular octagon, about the star of rhombuses in the exact centre of the picture.
A patch of hat tiling. The hat tiles are coloured in seven rainbow colours and two shades of grey, with the darker grey corresponding to the rare reflected hats. Again, the colour of each the hat indicates something about the pattern of neighbouring hats surrounding it, although in this case the colour doesn't uniquely determine a hat's entire neighbourhood.
The key to the previous diagram. Each of the seven chair colours is shown with a neighbourhood of surrounding chairs, each in a different pattern. These neighbourhoods are how the colours were chosen in the previous picture: each chair is coloured according to which of these patterns matches its neighbouring tiles, if it's rotated into the orientation shown here.
A patch of the 'chair' tiling, consisting of chairs (L-triominoes) organised in the plane via iteration of a substitution system in which each chair is expanded into four half-sized chairs that fill the same space.
In this picture, the chairs are in seven different rainbow colours, in a way that is not a proper 7-colouring (some clusters of adjacent yellow chairs can be seen), but appears to have some relation to the pattern of the tiling itself.