Self-similar fractals: An algorithmic point of view

This paper studies the self-similar fractals with overlaps from an algorithmic point of view. A decidable problem is a question such that there is an algorithm to answer “yes” or “no” to the question for every possible input. For a classical class of self-similar sets {E _b.d } _b,d where E _b.d = ∪ _i=1 ⁿ (E _b,d /d + b _i ) with b = (b ₁,…, b _n ) ∈ ? _n and d ∈ ? ∩ [n,∞), we prove that the following problems on the class are decidable: To test if the Hausdorff dimension of a given self-similar set is equal to its similarity dimension, and to test if a given self-similar set satisfies the open set condition (or the strong separation condition). In fact, based on graph algorithm, there are polynomial time algorithms for the above decidable problem.