Normalized information distance and the oscillation hierarchy

DOI10.1016/j.jcss.2021.08.006zbMath1481.68031arXiv1708.03583OpenAlexW3203762212MaRDI QIDQ2051851

Sebastiaan A. Terwijn, Wolfgang Merkle, Ambos-Spies, Klaus

Publication date: 25 November 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1708.03583

zbMATH Keywords

Kolmogorov complexitynormalized information distanceoscillation hierarchy

Mathematics Subject Classification ID

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

Related Items (1)

The Normalized Algorithmic Information Distance Can Not Be Approximated

Cites Work

• Unnamed Item
• Nonapproximability of the normalized information distance
• Classical recursion theory. Vol. II
• Algorithmic Randomness and Complexity
• The Similarity Metric
• Normalized Information Distance
• Information distance
• Fine hierarchies and Boolean terms
• The Normalized Algorithmic Information Distance Can Not Be Approximated
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Normalized information distance and the oscillation hierarchy