Error-Correction, and Finite-Delay Decodability
| dc.creator | Konstantinidis,Stavros | |
| dc.date | 2002 | |
| dc.date.accessioned | 2024-02-06T12:51:40Z | |
| dc.date.available | 2024-02-06T12:51:40Z | |
| dc.description | 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. | |
| dc.format | text/html | |
| dc.identifier | https://doi.org/10.3217/jucs-008-02-0278 | |
| dc.identifier | https://lib.jucs.org/article/27859/ | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/8111 | |
| dc.language | en | |
| dc.publisher | Journal of Universal Computer Science | |
| dc.relation | info:eu-repo/semantics/altIdentifier/eissn/0948-6968 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/pissn/0948-695X | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | J.UCS License | |
| dc.source | JUCS - Journal of Universal Computer Science 8(2): 278-291 | |
| dc.subject | channel | |
| dc.subject | decidability | |
| dc.subject | decoding delay | |
| dc.subject | error-correction | |
| dc.subject | error-detection | |
| dc.subject | regular language | |
| dc.subject | transducer | |
| dc.subject | unique decodability | |
| dc.title | Error-Correction, and Finite-Delay Decodability | |
| dc.type | Research Article |