Refined Bounds on Kolmogorov Complexity for ω-Languages | Zendy

Jöran Mielke | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Refined Bounds on Kolmogorov Complexity for ω-Languages

Author(s) -

Jöran Mielke

Publication year - 2008

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2008.12.016

Subject(s) - prefix , mathematics , kolmogorov complexity , descriptive complexity theory , hausdorff dimension , simple (philosophy) , hausdorff measure , outer measure , hausdorff space , discrete mathematics , complexity class , upper and lower bounds , fractal , measure (data warehouse) , regular language , combinatorics , time complexity , fractal dimension , theoretical computer science , computer science , minkowski–bouligand dimension , automaton , linguistics , mathematical analysis , philosophy , epistemology , database

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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research