Regular languages, property satisfiability, and shortcuts

Show simple item record

dc.contributor.advisor Konstantinidis, Stavros
dc.creator Melanson, Patrick
dc.date.accessioned 2021-06-16T15:37:54Z
dc.date.available 2021-06-16T15:37:54Z
dc.date.issued 2021
dc.identifier.uri http://library2.smu.ca/xmlui/handle/01/29606
dc.description 1 online resource (45 pages) : illustrations
dc.description Includes abstract.
dc.description Includes bibliographical references (pages 44-45).
dc.description.abstract The Language Server (LaSer ) is a website created to ask and answer various questions pertaining to regular languages. One of its main features is testing property satisfiability, that is, does a given regular language satisfy a particular property. If a regular language does satisfy the property, we can then ask if the language is maximal with respect to the property. That is, L is maximal if it is not properly contained in any language satisfying the property. Deciding if a language is maximal reduces to deciding if a language is universal, which is known to be PSPACE-complete. However, for some practical purposes, we need only know if a language is approximately maximal. That is p%-maximal. Using a randomized algorithm, we can check if a language is as maximal as we want, by repeatedly adding words and testing whether the language still satisfies the property. This new property is called pseudo-maximality, and is much easier to test. en_CA
dc.description.provenance Submitted by Greg Hilliard (greg.hilliard@smu.ca) on 2021-06-16T15:37:54Z No. of bitstreams: 1 Melanson_Patrick_Honours_2021.pdf: 374143 bytes, checksum: 40a3b5999ae364880e1ccce331dfe540 (MD5) en
dc.description.provenance Made available in DSpace on 2021-06-16T15:37:54Z (GMT). No. of bitstreams: 1 Melanson_Patrick_Honours_2021.pdf: 374143 bytes, checksum: 40a3b5999ae364880e1ccce331dfe540 (MD5) Previous issue date: 2021-06-06 en
dc.language.iso en en_CA
dc.publisher Halifax, N.S. : Saint Mary's University
dc.title Regular languages, property satisfiability, and shortcuts en_CA
dc.type Text en_CA
thesis.degree.name Bachelor of Science (Honours Mathematics)
thesis.degree.name Bachelor of Science (Honours Computing Science)
thesis.degree.level Undergraduate
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