Research and Proof of Decidability on Self-Similar Fractals

Abstract:

Some undecidability on self-affine fractals have been supported. In this paper, we research on the decidability for self-similar fractal of Dubes type. In fact, we prove that the following problems are decidable to test if the Hausdorff dimension of a given Dubes self-similar set is equal to its similarity dimension, and to test if a given Dubes self-similar set satisfies the strong separation condition.

• Periodical: Applied Mechanics and Materials (Volumes 511-512)
• Pages: 1185-1188
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.511-512.1185
• Online since: February 2014
• Authors: Min Jin
• Keywords: Decidability, Dube, Self-Similar Fractals

References

[1] Dijkstra, E. W.: A note on two problems in connexion with graphs. Numerische Mathematik 1 (1959) 269–271.

DOI: 10.1007/bf01386390

[2] Dube, S.: Undecidable problems in fractal geometry. Complex Systems 7 (1993) 423–444.

[3] Dube, S.: Fractal geometry, Turing machines and divide-and-conquer recurrences. RAIRO Inform. Théor. Appl. 28 (1994) 405–423.

DOI: 10.1051/ita/1994283-404051

[4] Falconer, K. J.: Fractal geometry. Mathematical foundations and applications. John Wiley & Sons Ltd., (1990).

[5] Sipser, M.: Introduction to the theory of computation. Course Technology, (2005).

[6] Wen, Z. Y.: Mathematical foundations of fractal geometry, Shanghai Scientific and Technological Education Publishing House, (2000).