Master’s Thesis Presentation • Algorithms and Complexity • Proving Properties of Fibonacci Representations via Automata Theory

Please note: This master’s thesis presentation will take place in DC 2310 and online.

Sonja Linghui Shan, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Jeffrey Shallit

We introduce a framework for mechanically testing, via automata theory, the completeness and unambiguity of Fibonacci-based representations, also called numeration systems. We illustrate its effectiveness and versatility by applying it to a diverse set of previously published and newly discovered representations. Additionally, if a representation is proved to be complete, we describe an algorithm, of O(log n) complexity, to find a representation for any particular number n.