Aperiodic Tilings V: The Refinable Frontier
8 days ago
- #substitution-systems
- #finite-state-transducers
- #aperiodic-tilings
- Simon Tatham discusses generating aperiodic tilings using string-processing techniques, focusing on finite-state transducers.
- The article explores the challenge of ambiguous substitution systems and presents a technique to construct unambiguous variations.
- Tatham introduces a refinement algorithm that clones tile types based on neighborhood patterns to remove ambiguities.
- The algorithm is demonstrated on the 'chair' tiling, reducing ambiguity by creating subtypes for different neighborhood configurations.
- The refined chair tiling successfully allows the construction of a deterministic transducer, overcoming previous limitations.
- The technique is applied to more complex tilings like HTPF (hats) and H7/H8 (Spectre), matching known unambiguous systems.
- An unexpected discovery: the algorithm produces a more economical substitution system for hats than previously known, with only 8 tile types.
- The article also covers the 'Awkward Squares' tiling, designed to test the algorithm's handling of difficult edge cases.
- Tatham concludes with the successful application of the refinement algorithm to the Ammann-Beenker tiling, correcting a previous transducer construction bug.