Error-Correction, and Finite-Delay Decodability

Stavros Konstantinidis (Department of Mathematics and Computing Science, Saint Mary's University, Canada)

Abstract: When the words of a language are communicated via a noisy channel, the language property of error-detection ensures that no word of the language can be transformed to another word of the language. On the other hand, the property of error-correction ensures that the channel cannot transform two different words of the language to the same word. In this work we use transducers to model noisy channels and consider a few simple transducer operations that can be used to reduce the language properties of error-detection and error-correction to the transducer property of functionality. As a consequence, we obtain simple polynomial-time algorithms for deciding these properties for regular languages. On the other hand the properties are not decidable for context-free languages. In addition we show that, in a certain sense, the class of rational channels can be used to model various error combinations. Using the same tools, we also obtain simple polynomial-time algorithms for deciding whether a given regular language is thin and whether a given regular code has decoding delay d, for given d, and for computing the minimum decoding delay of a given regular code.

Keywords: channel, decidability, decoding delay, error-correction, error-detection, regular language, transducer, unique decodability

Categories: F.