Abstract:
The paper investigates bounds on various notions of complexity for
w–languages. We understand the complexity of an w–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.