Strict Self-Assembly of Discrete Self-Similar Fractals in the abstract Tile-Assembly Model
<|reference_start|>Strict Self-Assembly of Discrete Self-Similar Fractals in the abstract Tile-Assembly Model: This paper answers a long-standing open question in tile-assembly theory, namely that it is possible to strictly assemble discrete self-similar fractals (DSSFs) in the abstract Tile-Assembly Model (aTAM). We prove this in 2 separate ways, each taking advantage of a novel set of tools. One of our constructions shows that specializing the notion of a quine, a program which prints its own output, to the language of tile-assembly naturally induces a fractal structure. The other construction introduces self-describing circuits as a means to abstractly represent the information flow through a tile-assembly construction and shows that such circuits may be constructed for a relative of the Sierpinski carpet, and indeed many other DSSFs, through a process of fixed-point iteration. This later result, or more specifically the machinery used in its construction, further enable us to provide a polynomial time procedure for deciding whether any given subset of $\mathbb{Z}^2$ will generate an aTAM producible DSSF. To this end, we also introduce the Tree Pump Theorem, a result analogous to the important Window Movie Lemma, but with requirements on the set of productions rather than on the self-assembling system itself.<|reference_end|>
@article{becker2024strict,
    title={Strict Self-Assembly of Discrete Self-Similar Fractals in the abstract
  Tile-Assembly Model},
    author={Florent Becker, Daniel Hader, Matthew J. Patitz},
    journal={arXiv preprint arXiv:2406.19595},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.19595},
    primaryClass={cs.CG}
}