Date of Award
Master of Science
Finite-state dimension is a computational version of classical Hausdorff (fractal) dimension that was recently developed by Dai, Lathrop, Lutz and Mayordomo. The finite-state dimension of an infinite binary sequence S is a real number dim[Subscriot FS](S) in [0,1] that characterizes the "information density" of S with respect to finite-state machines. It has been shown that the finite-state dimension of a sequence is the infimum of all compression ratios achievable by using finite-state lossless compressors on that sequence. In this thesis, we calculate the finite-state dimension of two specific binary sequences that have been extensively investigated, namely, the Thue-Morse sequence and the Kolakoski sequence. Along the way, we give an expository review of finite-state dimension and these two sequences.
Bachan, Mallika, "Finite-state dimension of the Kolakoski sequence" (2005). Retrospective Theses and Dissertations. 18893.