Refined Bounds on Kolmogorov Complexity for ω-Languages

The paper investigates bounds on various notions of complexity for ω–languages. We understand the complexity of an ω–languages as the complexity of the most complex strings contained in it. There have been shown bounds on simple and prefix complexity using fractal Hausdorff dimension. Here these bounds are refined by using general Hausdorff measure originally introduced by Felix Hausdorff. Furthermore a lower bound for a priori complexity is shown.