Maximal Error-Detecting Capabilities of Formal Languages
Stavros Konstantinidis, Pedro V. Silva · 2008
A (combinatorial) channel is a set of pairs of words describing all the possible inputoutput channel situations. We introduce the concept maximal error-detecting capability of a given language, with respect to a certain class of channels, which is simply a maximal channel for which the given language is error-detecting. 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.