6 Conditional automatic complexity

In this chapter we show that metrics analogous to the Jaccard distance and the Normalized Information Distance can be defined based on conditional nondeterministic automatic complexity $A_N$. Our work continues the path of Shannon (1950) on entropy metrics and Gács (1974) on symmetry of information among others.

Shallit and Wang (2001) defined the automatic complexity of a word $w$ as, somewhat roughly speaking, the minimum number of states of a finite automaton that accepts $w$ and no other word of length $|w|$. This definition may sound a bit artificial, as it is not clear the length of $w$ is involved in defining the complexity of $w$. In this chapter we shall see how conditional automatic complexity neatly resolves this issue.

6.1 Basics