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
DOI: https://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.