Maximal Error-Detecting Capabilities of Formal Languages1

A combinatorial channel is a set of pairs of words describing all the possible input-output channel situations. We introduce the concept “maximal error-detecting capability ” of a formal language, with respect to a certain class of combinatorial channels. The new concept is intended to address formally the question of “finding the largest amount of errors that a language can detect”. We focus on rational channels (those described by finite transducers) and on regular languages, and consider the problem of computing maximal error-detecting capabilities of a given regular language for various classes of rational channels. We also discuss briefly the concept “maximal error-correcting capability ” of a formal language