Crate substitution_tiling_transducers 

This crate implements a suite of algorithms for dealing with substitution tilings of the plane, including aperiodic tilings such as the Penrose tilings and the 2023 Hat and Spectre tilings.

The core concept in this crate is the ‘transducer’ described in ‘Finite-state transducers for substitution tilings’. (This Rust crate is the companion code to that paper, in fact.) A brief summary:

In a substitution tiling system, each tile can be assigned an ‘address’ which states its position in the substitution hierarchy in purely symbolic terms, by giving the type of the tile and all its higher-order supertiles, and at each step, indicating which subtile of the supertile was selected. An address of one tile in a tiling can be converted into the address of its neighbour, using a finite state machine which consumes the address one symbol at a time and outputs the address of the neighbouring tile. This provides a practical way to plot patches of aperiodic tilings, as well as permitting various analyses of the substitution system.

This crate implements the workflow for building a transducer:

• start from a combinatorial description of the substitution system (CombSystem), which specifies how tiles connect and relate to each other without saying anything about their shapes and sizes

• from that, build a preliminary ‘adjacency recogniser’ state machine (Recogniser), which takes two tile addresses and determine whether they are neighbours along specified edges

• from that in turn, build a transducer (Transducer) which takes one tile address and outputs its neighbour along a specified edge

• if the transducer cannot be built due to an ambiguity in the original system, automatically refine the system by cloning tile types into subtypes, producing a specification of the refinement (Refinement) which can be combined with the original CombSystem to produce a new one.

Optionally, a CombSystem can be constructed from a geometric description of the tiling (GeomSystem). If you have a geometric description of the tiling, you can also use the transducer to plot patches of tiles, via three different algorithms (PushGenerator, RasterGenerator, SearchGenerator), all with different strengths and weaknesses. Patches can be generated based on user-specified tile addresses, or based on a random tile address.

This crate supports loading and saving many of its data types as TOML-based file formats. In the toml data directory of its source, sample files are provided which define well-known aperiodic tilings.

Modules

address

Types for representing the combinatorial address of a tile.

automata

General data types for finite automata.

builtin

Ready-made substitution systems.

combinatorial

Combinatorial substitution systems and algorithms.

common

Common definitions across the crate.

cosmetics

Systems for choosing the appearance of a tile.

filetype

Identify types of files used by this crate.

generators

Algorithms to generate patches of actual tiling.

geometric

Geometric specification of a substitution system.

polyring

Arithmetic on elements of a polynomial ring.

randomaddr

Tools for randomly generating tile addresses.