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.
Distances between languages and reflexivity of relations / C. Choffrut, G. Pighizzini. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 286:1(2002 Sep 06), pp. 117-138.
Distances between languages and reflexivity of relations
G. PighizziniUltimo
2002
Abstract
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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.