Name
Abstract | ||
|---|---|---|
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. Key Words: channel, decidability, decoding delay, error-correction, error-detection, regular language, transducer, unique decodability. Category: F |
Year | Venue | Keywords |
|---|---|---|
2002 | J. UCS | regular language,error detection,error correction,context free language |
Field | DocType | Volume |
Computer science,Algorithm,Error detection and correction | Journal | 8 |
Issue | Citations | PageRank |
2 | 4 | 0.46 |
References | Authors | |
2 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stavros Konstantinidis | 1 | 283 | 31.10 |