A correspondence principle for finite state dimension
Anumodh Abey · 2004
Classical Hausdorff dimension was recently characterized using mathematical functions called s-gales which are generalizations of martingales. It laid the foundation for the development of theory of resource-bounded dimension that has applications in complexity theory. This work deals with finite-state dimension where the s-gale has to be computable using finite-state machines. The research problem addressed in this work is to determine sets of sequences in Cantor Space (i.e., sets of binary sequences for which the Hausdorff dimension and finite-state dimension are equal). This is known as the correspondence principle for finite-state dimension. We prove that any [omega]-regular language (i.e., set of binary sequences accepted by a Buchi automaton) satisfies the correspondence principle.