Computing error-detecting capabilities of regular languages

Abstract

The property of error-detection ensures that when words of a language are communicated over a noisy channel, no word of the language can be transformed into another word of the language. The newer concept of maximal error-detecting capability seeks to find the noisiest channel a language is error-detecting for. We investigate, refine and implement algorithms related to error-detection for regular languages (words accepted by a finite automaton). As a result, we present some new ways of modeling channels using sequential machines. In addition, we adapt an existing transducer functionality algorithm to work with sequential machines, for the purpose of deciding the error-detection property. In the process we introduce, among others, the new concept of pseudo-sequential machines, and provide methods for converting them to sequential machines and vice-versa. We apply our new tools to the higher concept, and the result is a way of computing the maximal error-detecting capabilities of a regular language. We have implemented the new algorithms we developed, as well as some relevant existing theoretical algorithms. Finally, we have created a web interface for interacting with the tools we developed, and have made the source code of our implementation available to the research community.