On the Decidability of the Error-Detection Property

			Stavros Konstantinidis

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.
In this work we model channels using finite transducers and we show 
that the problem of whether a given regular language is 
error-detecting for a given rational channel can be decided in 
polynomial time. On the other hand, the problem is undecidable for 
context-free languages. Moreover, we demonstrate constructively that 
the class of rational channels includes all the SID-channels which 
can be used to model the effects of various error combinations. 
Finally, we briefly discuss the properties of error-correction and 
unique decodability for rational channels.