diff options
| -rw-r--r-- | README.md | 39 |
1 files changed, 39 insertions, 0 deletions
diff --git a/README.md b/README.md new file mode 100644 index 0000000..423eb4f --- /dev/null +++ b/README.md @@ -0,0 +1,39 @@ +# MSO Question Answering on Trees + +This is my Master's thesis, defended on December 20, 2022 at MIM UW. Also +included are the slides I used for the defense presentation. + +## 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 |