<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T16:52:59Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/1034" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/1034</identifier><datestamp>2017-03-21T19:37:57Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" lang="en" authority="2356c63b-193c-41a6-b532-df2e3e249e19" confidence="600">Krawetz, Bryan</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2006-08-22T14:25:54Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2006-08-22T14:25:54Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2004</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2004</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/1034</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">In this thesis, we cover the general topic of state complexity.   In particular, we examine the bounds on the state complexity of some different representations of regular languages.   As well, we consider the state complexity of the operation root(&amp;lt;i&amp;gt;L&amp;lt;/i&amp;gt;).      
We give quick treatment of the deterministic state complexity bounds for nondeterministic finite automata and regular expressions.   This includes an improvement on the worst-case lower bound for a regular expression, relative to its alphabetic length.      
The focus of this thesis is the study of the increase in state complexity of a regular language &amp;lt;i&amp;gt;L&amp;lt;/i&amp;gt; under the operation  root(&amp;lt;i&amp;gt;L&amp;lt;/i&amp;gt;).    This operation requires us to examine the connections between abstract algebra and formal languages.      
We present results, some original to this thesis, concerning the size of the largest monoid generated by two elements.   Also, we give good bounds on the worst-case state complexity of root(&amp;lt;i&amp;gt;L&amp;lt;/i&amp;gt;).   In turn, these new results concerning root(&amp;lt;i&amp;gt;L&amp;lt;/i&amp;gt;) allow us to improve previous bounds given for the state complexity of two-way deterministic finite automata.</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">493885 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="rights" lang="en">Copyright: 2004, 
  Krawetz, Bryan. All rights reserved.</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">state complexity</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">monoids</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">formal languages</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">regular languages</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Monoids and the State Complexity of the Operation root(&amp;lt;i&amp;gt;L&amp;lt;/i&amp;gt;)</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>