Combinatorial information distance

Let |A|
denote the cardinality of a finite set A
. For any real number x
define t(x)=x
if x≥1
and 1 otherwise. For any finite sets A,B
let δ(A,B)
=
log2(t(|B∩A¯||A|))
. We define {This appears as Technical Report # arXiv:0905.2386v4. A shorter version appears in the {Proc. of Mini-Conference on Applied Theoretical Computer Science (MATCOS-10)}, Slovenia, Oct. 13-14, 2010.} a new cobinatorial distance d(A,B)
=
max{δ(A,B),δ(B,A)}
which may be applied to measure the distance between binary strings of different lengths. The distance is based on a classical combinatorial notion of information introduced by Kolmogorov.