<?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-22T12:22:26Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/5162" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/5162</identifier><datestamp>2017-03-21T18:00:31Z</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" authority="bf8462db-d67f-433d-86b5-33c57ab64a17" confidence="600">Ang, Thomas</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2010-05-11T13:56:25Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2010-05-11T13:56:25Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2010-05-11T13:56:25Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2010</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/5162</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">In formal language theory, studying shortest strings in languages, and variations thereof, can be useful since these strings can serve as small witnesses for properties of the languages, and can also provide bounds for other problems involving languages. For example, the length of the shortest string accepted by a regular language provides a lower bound on the state complexity of the language.&#xd;
&#xd;
In Chapter 1, we introduce some relevant concepts and notation used in automata and language theory, and we show some basic results concerning the connection between the length of the shortest string and the nondeterministic state complexity of a regular language. Chapter 2 examines the effect of the intersection operation on the length of the shortest string in regular languages. A tight worst-case bound is given for the length of the shortest string in the intersection of two regular languages, and loose bounds are given for two variations on the problem. Chapter 3 discusses languages that are defined over a free group instead of a free monoid. We study the length of the shortest string in a regular language that becomes the empty string in the free group, and a variety of bounds are given for different cases. Chapter 4 mentions open problems and some interesting observations that were made while studying two of the problems: finding good bounds on the length of the shortest squarefree string accepted by a deterministic finite automaton, and finding an efficient way to check if a finite set of finite words generates the free monoid.&#xd;
 &#xd;
Some of the results in this thesis have appeared in work that the author has participated in \cite{AngPigRamSha,AngShallit}.</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="subject" lang="en">automata theory</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">algorithms and complexity</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">finite state machine</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">regular languages</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">regular expressions</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">formal languages</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">theory of computation</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Problems Related to Shortest Strings in Formal Languages</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>