Multidimensional shift spaces achieved using substitution sequences
Pimp my fixpoint: sofic realization of multidimensional substitution-based shift spaces
Discrete Mathematics
Summary
Some math problems study patterns that repeat in complicated ways across many directions. This paper explains a new way to build these patterns using sequences of substitutions that grow in size, making it easier to understand and recognize certain complex patterns called sofic shift spaces. The authors give a clear rule that shows when these patterns can be described by simpler, more manageable models. Their work extends earlier examples and helps identify new classes of these patterns in multiple dimensions.
What this means in practice
- •For computational systems designers: Identify when complex multidimensional symbolic patterns can be efficiently represented to optimize storage or processing in system design.
- •For mathematical software developers: Implement algorithms for constructing multidimensional sofic shift spaces based on substitution sequences for simulation or visualization tools.
A theory result. No direct application yet.
Authors
Antonin Callard, Pierre Guillon, Léo Paviet Salomon, Pascal Vanier
Abstract
In symbolic dynamics, the fixed-point construction from arXiv:0910.2415 defines shift spaces of finite type whose configurations embed infinite hierarchies of tilings. This article provides a "black box" abstraction of this method phrased in terms of substitutions and $S$-adic limit spaces operating over sequences of increasingly large alphabets. By quantifying the amount of information computed by the substitutions at each level, and using a suitable parallel model of computation, we provide a simple positive criterion of multidimensional soficity that generalizes classical examples from the literature.