A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law

DOI10.1016/0020-0190(95)00201-4MaRDI QIDQ672725zbMATH OpenOpenAlexFDO

Authors Marius Zimand

Publication date 28 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(95)00201-4

zbMATH Keywords

Kolmogorov complexityLogical definabilityProbability asymptotics

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• The Kolmogorov expression complexity of logics
• 0-1 laws for recursive structures
• scientific article; zbMATH DE number 58300

Cites work

• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• scientific article; zbMATH DE number 736618 (Why is no real title available?)
• scientific article; zbMATH DE number 1142293 (Why is no real title available?)
• scientific article; zbMATH DE number 6157246 (Why is no real title available?)
• Infinitary logics and 0-1 laws
• On Languages Reducible to Algorithmically Random Languages
• Optimization, approximation, and complexity classes
• Probabilities on finite models
• The Kolmogorov expressive power of Boolean query languages

Cited in

(2)

• 0-1 laws for recursive structures
• The Kolmogorov expression complexity of logics

This page was built for publication: A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672725)