Computing error-detecting capabilities of regular languages

Show simple item record

dc.contributor.advisor Konstantinidis, Stavros
dc.creator Daka, Alifasi 2012-09-04T19:23:25Z 2012-09-04T19:23:25Z 2011
dc.identifier.other QA268 D35 2011
dc.description vi, 115 leaves : ill. ; 29 cm. en_CA
dc.description Includes abstract.
dc.description Includes bibliographical references (leaves 111-115).
dc.description.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. en_CA
dc.description.provenance Submitted by Dianne MacPhee ( on 2012-09-04T19:23:25Z No. of bitstreams: 0 en
dc.description.provenance Made available in DSpace on 2012-09-04T19:23:25Z (GMT). No. of bitstreams: 0 Previous issue date: 2011 en
dc.language.iso en en_CA
dc.publisher Halifax, N.S. : Saint Mary's University en_CA
dc.subject.lcc QA268
dc.subject.lcsh Error-correcting codes (Information theory)
dc.subject.lcsh Formal languages
dc.title Computing error-detecting capabilities of regular languages en_CA
dc.type Text en_CA Master of Science in Applied Science Masters Mathematics and Computing Science Saint Mary's University (Halifax, N.S.)
 Find Full text

Files in this item


This item appears in the following Collection(s)

Show simple item record

Search DSpace


My Account