A4 Refereed article in a conference publication
Undecidable Properties of Self-affine Sets and Multi-tape Automata
Authors: Timo Jolivet, Jarkko Kari
Editors: Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik
Conference name: International symposium on mathematical foundations of computer science 2014
Publication year: 2014
Journal: Lecture Notes in Computer Science
Book title : Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014: Budapest, Hungary, August 25-29, 2014: Proceedings, Part I
Series title: Lecture Notes in Computer Science
Volume: 8634
First page : 352
Last page: 364
Number of pages: 13
ISBN: 978-3-662-44521-1
eISBN: 978-3-662-44522-8
ISSN: 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.
