摘要
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=Sn i=1(E b,d/d+b i)with b=(b1,...,b n)∈Qn and d∈N∩[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.
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=Sn i=1（E b,d/d＋b i）with b=（b1,...,b n）∈Qn and d∈N∩[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.
基金
supported by National Natural Science Foundation of China(Grants Nos.11071224 and 11371329)
Program for New Century Excellent Talents in University
Natural Science Foundation of Zhejiang Province(Grants Nos.LY12F02011 and LR13A1010001)
Foundation of Zhejiang Educational Committee(Grant No.Y201226044)
