# 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
```