Degree Type

Thesis

Date of Award

1-1-2005

Degree Name

Master of Science

Major

Computer Science

Abstract

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.

Copyright Owner

Mallika Bachan

Language

en

OCLC Number

63192260

File Format

application/pdf

File Size

39 pages

Share

COinS