Conditional automatic complexity and its metrics

Abstract

Li, Chen, Li, Ma, and Vitányi (2004) introduced a similarity metric based on Kolmogorov complexity. It followed work by Shannon in the 1950s on a metric based on entropy. We define two computable similarity metrics, analogous to the Jaccard distance and Normalized Information Distance, based on conditional automatic complexity and show that they satisfy all axioms of metric spaces.

arXiv comment29th International Computing and Combinatorics Conference (COCOON 2023), Lecture Notes in Computer Science