Master’s Thesis Presentation • Algorithms and Complexity • Automata and Ratio Sets

Please note: This master’s thesis presentation will take place online.

Joseph Meleshko, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Jeffrey Shallit

I explore the composition of ratio sets, the subsets of the rationals derived from the quotients of two sets of natural numbers, and examine a variety of specific examples where the comprising sets of natural numbers have specific properties. I present a general algorithm that decides the inclusion of a rational number in a specific ratio set if the comprising sets of natural numbers are a regular language when represented in a given base. I also present an algorithm for deciding the inclusion of a rational number in the ratio set of a few select sets of natural numbers that are not a regular language when represented in any base, namely, the set of natural numbers with representations in a specific base that are palindromes or antipalindromes. Using those algorithms, I examine some of the rational numbers in specific ratio sets and then prove several results regarding the composition of those ratio sets. As well, I present algorithms for computing approximations to real numbers using elements of some specific ratio sets.

To join this master’s thesis presentation on Zoom, please go to https://uwaterloo.zoom.us/j/91780244361.