Exact Expression For Information Distance
This work addresses a theoretical problem in information theory by extending information distance concepts to multisets, but it appears incremental as it builds on existing Kolmogorov complexity frameworks.
The paper tackles the problem of defining and computing information distance for multisets of strings, providing an exact expression in terms of plain Kolmogorov complexity with a proof that the lower bound equals the upper bound up to a constant additive term for each cardinality.
Information distance can be defined not only between two strings but also in a finite multiset of strings of cardinality greater than two. We give an elementary proof for expressing the information distance in terms of plain Kolmogorov complexity. It is exact since for each cardinality of the multiset the lower bound for some multiset equals the upper bound for all multisets up to a constant additive term.