Application and implementation of transducer tools in answering certain questions about regular languages

Show simple item record

dc.contributor.advisor Konstantinidis, Stavros
dc.creator Yang, Meng
dc.date.accessioned 2012-12-14T19:28:17Z
dc.date.available 2012-12-14T19:28:17Z
dc.date.issued 2012
dc.identifier.other QA267.3 Y36 2012
dc.identifier.uri http://library2.smu.ca/xmlui/handle/01/24794
dc.description 121 leaves : ill. ; 29 cm.
dc.description Includes abstract.
dc.description Includes bibliographical references (leaves 117-121).
dc.description.abstract In this research, we investigate, refine, and implement algorithmic tools that allow us to answer decision questions about regular languages. We provide a thorough presentation of existing algorithmic tools to answer the satisfaction questions of whether a given language satisfies a given property described by an input-preserving transducer, which is equivalent to the question of whether a given language is error-detecting for the channel realized by the same input-preserving transducer; whether a given language is error-correcting for the channel realized by an input-preserving transducer; whether a given regular language satisfies the code property. In the process, we give a thorough presentation of an existing algorithm to decide whether a transducer is functional and an algorithm about how to translate a normal form transducer into a real-time transducer. We also introduce our method to provide counterexamples in cases where the answers to the satisfaction questions are negative. In addition, we discuss our new method to estimate the edit distance of a regular language by the error-correction property, which is much faster than the existing method of computing the edit distance via error-detection. Finally, we deliver an open implementation of these algorithms and methods via a web interface – I-LaSer, and add the implementation of transducer classes into our copy of the FAdo libraries. en_CA
dc.language.iso en en_CA
dc.publisher Halifax, N.S. : Saint Mary's University
dc.subject.lcc QA267.3
dc.subject.lcsh Formal languages
dc.subject.lcsh Algorithms
dc.title Application and implementation of transducer tools in answering certain questions about regular languages en_CA
dc.type Text en_CA
thesis.degree.name Master of Science in Applied Science
thesis.degree.level Masters
thesis.degree.discipline Mathematics and Computing Science
thesis.degree.grantor Saint Mary's University (Halifax, N.S.)


Files in this item

 
 

This item appears in the following Collection(s)

Show simple item record