What is a Maximal Error-Detecting Capability of a Formal Language?

                            Stavros Konstantinidis

We introduce the concepts ``maximal error-correcting capability''
and ``maximal error-detecting capability'' of a given formal
language (set of words), with respect to a certain class of
combinatorial channels. A combinatorial channel is a set of pairs of
words describing all the possible input/output channel situations.
This paper is mainly intended to obtain basic general results on
these new concepts and discuss possible research directions with an
emphasis on the problem of computing maximal error-detecting (or
-correcting) capabilities of a given regular language.