Papers for

computational systems designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Multidimensional shift spaces achieved using substitution sequences

Pimp my fixpoint: sofic realization of multidimensional substitution-based shift spaces

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.

Wed 23 SeptDiscrete Mathematics

The gist

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.

Open → 2609.28207v1