Undecidable Properties of Self-affine Sets and Multi-tape Automata




Timo Jolivet, Jarkko Kari

Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik

International symposium on mathematical foundations of computer science 2014

2014

Lecture Notes in Computer Science

Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014: Budapest, Hungary, August 25-29, 2014: Proceedings, Part I

Lecture Notes in Computer Science

8634

352

364

13

978-3-662-44521-1

978-3-662-44522-8

0302-9743

DOIhttps://doi.org/10.1007/978-3-662-44522-8_30



We study the decidability of the topological properties of some objects coming from fractal geometry. We prove that having empty interior is undecidable for the sets defined by two-dimensional graph-directed iterated function systems. These results are obtained by studying a particular class of self-affine sets associated with multi-tape automata. We first establish the undecidability of some language-theoretical properties of such automata, which then translate into undecidability results about their associated self-affine sets.



Last updated on 2024-26-11 at 18:52