Self-similar fractals: An algorithmic point of view  

作　　者：WANG Qin XI LiFeng ZHANG Kai 

机构地区：[1]Department of Computer Science,Zhejiang Wanli University [2]Institute of Mathematics,Zhejiang Wanli University [3]Junior College,Zhejiang Wanli University

出　　处：《Science China Mathematics》2014年第4期755-766,共12页中国科学：数学（英文版）

基　　金：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)

摘　　要：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.

关 键 词：FRACTAL DECIDABILITY DIMENSION separation condition 

分 类 号：O189[理学—数学]