Effective fractal dimension: foundations and applications

Thumbnail Image
Hitchcock, John
Major Professor
Jack H. Lutz
Committee Member
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Organizational Unit
Computer Science

Computer Science—the theory, representation, processing, communication and use of information—is fundamentally transforming every aspect of human endeavor. The Department of Computer Science at Iowa State University advances computational and information sciences through; 1. educational and research programs within and beyond the university; 2. active engagement to help define national and international research, and 3. educational agendas, and sustained commitment to graduating leaders for academia, industry and government.

The Computer Science Department was officially established in 1969, with Robert Stewart serving as the founding Department Chair. Faculty were composed of joint appointments with Mathematics, Statistics, and Electrical Engineering. In 1969, the building which now houses the Computer Science department, then simply called the Computer Science building, was completed. Later it was named Atanasoff Hall. Throughout the 1980s to present, the department expanded and developed its teaching and research agendas to cover many areas of computing.

Dates of Existence

Related Units

Journal Issue
Is Version Of

Lutz characterized Hausdorff dimension using gales, gambling functions which generalize martingales. Imposing computability and complexity constraints on the gales in this characterization gives the constructive and resource-bounded dimensions. These effective dimensions are useful measures of complexity for theoretical computer science and are closely related to other measures of complexity including Kolmogorov complexity, Boolean circuit-size complexity, and predictability.;This thesis makes several foundational contributions to effective fractal dimension. We show that packing dimension, despite the greater complexity of its definition, can also be effectivized using gales. This is used to introduce constructive strong dimension and resource-bounded strong dimension. The theory of effective strong dimension is presented alongside that of effective dimension, emphasizing the duality between the two types of dimension. We show that gales and supergales are equivalent for defining the constructive dimensions, and that the constructive dimensions can be characterized using constructive entropy rates. The resource-bounded dimensions are characterized by log-loss unpredictability in a standard model of prediction. Characterizations of the computability and polynomial-space dimensions involving resource-bounded Kolmogorov complexity and entropy rates are given.;Relationships between constructive dimension and the arithmetical hierarchy are investigated. We identify the levels of the arithmetical hierarchy in which the Hausdorff and constructive dimensions of a set are guaranteed to be equal. The constructive dimension classes are precisely located in the arithmetical hierarchy.;We use resource-bounded dimension to investigate complexity classes involving polynomial-time reductions. Resource-bounded scaled dimension is applied to extend the small span theorem of resource-bounded measure. We show that degrees of arbitrary dimension and strong dimension exist within exponential time. The dimensions of classes that are reducible to nondense languages are investigated.

Subject Categories
Wed Jan 01 00:00:00 UTC 2003