Distances between languages and reflexivity of relations

We extend the Hamming, edit, prefix, suffix and subword distances between strings to subsets of strings. We show that computing these distances between two rational subsets reduces to computing the weight of an automaton "with distance function" as introduced by Hashiguchi (this latter notion of distance has nothing to do with our notion). We make a step further by extending the notion of distance between subsets to that of "almost reflexivity" of relations over strings: intuitively a relation is almost reflexive if every element of its domain is in relation with some "close" element in its range and vice versa. Various properties connected to almost reflexivity are investigated. With two exceptions, their decidability status relative to the five notions of distances is settled for the three families of recognizable, synchronous and deterministic relations. (C) 2002 Elsevier Science B.V. All rights reserved.