| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 421997 | Electronic Notes in Theoretical Computer Science | 2008 | 9 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
