Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 8 / Issue 2

available in:   PDF (196 kB) PS (170 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-008-02-0278


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.

1.) C. S. Calude, K. Salomaa, S. Yu (eds.). Advances and Trends in Automata and Formal Languages. A Collection of Papers in Honour of the 60th Birthday of Helmut J├╝rgensen.

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

Categories: F.