A system for describing and deciding properties of regular languages using input altering transducers

Show simple item record

dc.contributor.advisor Konstantinidis, Stavros
dc.creator Dudzinski, Krystian
dc.date.accessioned 2012-10-25T20:25:55Z
dc.date.available 2012-10-25T20:25:55Z
dc.date.issued 2011
dc.identifier.other QA267.3 D83 2011
dc.identifier.uri http://library2.smu.ca/xmlui/handle/01/24743
dc.description ii, 94 leaves : ill. ; 29 cm. en_CA
dc.description Includes abstract.
dc.description Includes bibliographical references (leaves 92-94).
dc.description.abstract We present a formal method for describing and deciding code related properties of regular languages using input altering transducers. We also provide an implementation of that method in the form of a web application. We introduce the concept of an input altering transducer. We show how to use such transducers to describe properties of languages and present examples of transducers describing some well known properties (like suffix codes, prefix codes, infix codes, solid codes, and others). We discuss some limitations of our method. In particular, all properties that can be described using input altering transducers are 3-independence properties. We also give an example of a 3-independence property that cannot be represented using a transducer. We explain how our method is a specialisation of a more general method based on language in-equations. We also discuss the relation between our method and a method that uses sets of trajectories to describe properties. In particular, we show how, for any given set of trajectories describing some property, to build an input altering transducer describing the same property. We introduce the concept of counterexample, which is a pair of words that, if a given language does not belong to a given property, illustrate that fact. We show how we can incorporate extracting such counterexample into our method. Finally, we provide some details on the implementation and usage of the web application that was built as a part of this research. en_CA
dc.description.provenance Submitted by Dianne MacPhee (dianne.macphee@smu.ca) on 2012-10-25T20:25:55Z No. of bitstreams: 0 en
dc.description.provenance Made available in DSpace on 2012-10-25T20:25:55Z (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 QA267.3
dc.subject.lcsh Formal languages
dc.subject.lcsh Machine theory
dc.title A system for describing and deciding properties of regular languages using input altering transducers 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.)
 Find Full text

Files in this item


This item appears in the following Collection(s)

Show simple item record

Search DSpace


My Account