Affiliations: Department of Mathematics and Computing Science, Saint Mary’s University, Halifax, Nova Scotia, B3H 3C3 Canada. s.konstantinidis@smu.ca | Centro de Matemática, Faculdade de Ciências, Universidade do Porto – R. Campo Alegre 687, 4169-007 Porto, Portugal. pvsilva@fc.up.pt
Note: [] Address for correspondence: Department of Mathematics and Computing Science, Saint Mary’s University, Halifax, Nova Scotia, B3H 3C3 Canada
Abstract: 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 any combination of the basic error 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 γ if and only if it is error-detecting for the inverse of γ. 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.
