A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Undecidable Properties of Self-affine Sets and Multi-tape Automata
Tekijät: Timo Jolivet, Jarkko Kari
Toimittaja: Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik
Konferenssin vakiintunut nimi: International symposium on mathematical foundations of computer science 2014
Julkaisuvuosi: 2014
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014: Budapest, Hungary, August 25-29, 2014: Proceedings, Part I
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 8634
Aloitussivu: 352
Lopetussivu: 364
Sivujen määrä: 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.
