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.description.provenance |
Submitted by Trish Grelot (trish.grelot@smu.ca) on 2012-12-14T19:28:17Z
No. of bitstreams: 1
yang_meng_masters_2012.pdf: 1803200 bytes, checksum: 0e90cfc70343e25c441a253e5ce143d1 (MD5) |
en |
dc.description.provenance |
Made available in DSpace on 2012-12-14T19:28:17Z (GMT). No. of bitstreams: 1
yang_meng_masters_2012.pdf: 1803200 bytes, checksum: 0e90cfc70343e25c441a253e5ce143d1 (MD5) |
en |
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.) |
|