Error-Detecting Properties of Languages

           Stavros Konstantinidis

In the context of storing/transmitting words of a language
$L$ using a noisy medium, the language property of
error-detection is fundamental. It ensures that the medium cannot
transform a word from $L$ to another word of $L$. 
This paper defines some basic error-detecting  properties of
languages and obtains a few basic results on error-detection.
For example, it is shown that the number of synchronization errors
that a regular language can detect is bounded by the size of its
syntactic monoid. Moreover, some error-detecting capabilities of 
uniform, solid, and shuffle
codes are considered. It is shown that those codes 
provide certain error-detection either for free or when a simpler
condition is satisfied.