<?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-22T19:57:25Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/15845" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/15845</identifier><datestamp>2025-03-26T23:35:50Z</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="7f88ec43-57b8-446d-b69b-357fdd19cc34" confidence="600">Baranwal, Aseem</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2020-05-13T20:38:25Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2020-05-13T20:38:25Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2020-05-13</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2020-05-08</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/15845</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">We extend the notion of automatic sequences to a broader class, the Ostrowski-automatic sequences. We develop a procedure for computationally deciding certain combinatorial and enumeration questions about such sequences that can be expressed as predicates in first-order logic.&#xd;
&#xd;
In Chapter 1, we begin with topics and ideas that are preliminary to this work, including a small introduction to non-standard positional numeration systems and the relationship between words and automata. In Chapter 2, we define the theoretical foundations for recognizing addition in a generalized Ostrowski numeration system and formalize the general theory that develops our decision procedure. Next, in Chapter 3, we show how to implement these ideas in practice, and provide the implementation as an integration to the automatic theorem-proving software package -- Walnut.&#xd;
Further, we provide some applications of our work in Chapter 4. These applications span several topics in combinatorics on words, including repetitions, pattern-avoidance, critical exponents of special classes of words, properties of Lucas words, and so forth. Finally, we close with open problems on decidability and higher-order numeration systems and discuss future directions for research.</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">decision procedures</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Ostrowski numeration</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">repetitions</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">combinatorics on words</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">palindrome-richness</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">automatic sequences</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Decision Algorithms for Ostrowski-Automatic Sequences</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" 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>