Abstract:
We study automata-theoretic properties of distances and quasi-distances between
words. We show that every additive distance is finite. We also show that every
additive quasi-distance is regularity-preserving, that is, the neighborhood of any
radius of a regular language with respect to an additive quasi distance is regular. As
an application we present a simple algorithm that constructs a metric (fault-tolerant)
lexical analyzer for any given lexical analyzer and desired radius (fault-tolerance
index).
