2023/08/30 by Kjos-Hanssen, Bjørn
#FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic (math.LO)
paper · doi:10.48550/arxiv.2308.16292
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.