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$.