Add README

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