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 \(\lvert w\rvert \). 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.