Computing Maximal Error-detecting Capabilities and Distances
of Regular Languages
Stavros Konstantinidis and Pedro V. Silva
A (combinatorial) channel consists of pairs of words representing all
possible input-output channel situations. In a past paper, we formalized
the intuitive concept of ``largest amount of errors'' detectable by a
given language $L$, by defining the maximal error-detecting capabilities
of $L$ with respect to a given class of channels, and we showed how to
compute all maximal error-detecting capabilities (channels) of a given
regular language with respect to the class of rational channels and a
class of channels involving only the substitution-error type. In this
paper we resolve the problem for channels involving errors of any
combination of the basic types substitution, insertion, deletion.
Moreover, we consider the problem of finding the inverses of these
channels, in view of the fact that $L$ is error-detecting for $\gamma$
if and only if it is error-detecting for the inverse of $\gamma$. We also
discuss a natural method of reducing the problem of computing (inner)
distances of a given regular language $L$ to the problem of computing
maximal error-detecting capabilities of $L$.