MSO Question Answering on Trees

This is the LaTeX source for my Master's thesis, defended on December 20, 2022 at MIM UW. Also included are the Markdown slides I used for the defense presentation.

You can check out the actual PDFs here:

Abstract

We define relabel regular questions on trees, which, via the known equivalence between tree automata and MSO formulae on trees, happens to be a generalization of the MSO query answering problem on trees. We show these questions can be answered in time O_φ(m log(m)) with respect to question size (constant time in the case of MSO formulae with only first-order free variables) after preprocessing the input tree in time linear with respect to the tree's size. Along the way, we show an algorithm for answering questions of the form "Does the infix of a tree branch between nodes x and y belong to the regular language L" (for a previously fixed regular language L) in constant time after linear preprocessing. Our approach is much simpler in presentation than if using deterministic factorization forests due to Colcombet.

Building the PDFs

Dependencies:

LaTeX (including various packages)
Biber
Inkscape (for embedding SVGs in LaTeX)
Pandoc (for building the presentation)

If you have all those installed, you should be able to build both PDFs with just

make

To build just the thesis:

make mgr.pdf

To build just the presentation:

make presentation