<?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-22T18:57:06Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/20258" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/20258</identifier><datestamp>2025-03-26T23:35:28Z</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="advisor">Shallit, Jeffrey</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="c3045891-4f0b-4785-a29f-7aa4909740cc" confidence="600">Shan, Sonja Linghui</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2024-01-22T15:14:48Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2024-01-22T15:14:48Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2024-01-22</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2024-01-10</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/20258</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">In this work, we introduce a novel framework for mechanically testing the completeness and unambiguity of Fibonacci-based representations via automata theory. We call a representation (or a number system) complete and unambiguous when it provides one and only one representation for each number in the range covered by the representation. Many commonly used representations are complete and unambiguous: consider the familiar binary number system—each natural number has a unique representation up to leading zeros. Additionally, if a representation is complete, we describe an algorithm, of O(log n)&#xd;
complexity, to find a representation for any particular number n.</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">numeration systems</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Fibonacci numbers</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Proving Properties of Fibonacci Representations via Automata Theory</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">David R. Cheriton School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws-etd" element="embargo" qualifier="terms" lang="en">0</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Shallit, Jeffrey</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</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>