Add first version of abstract

1 files changed, 9 insertions, 1 deletions

diff --git a/mgr.tex b/mgr.tex
index 1a727ed..37bc034 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -41,7 +41,15 @@
 
 %tu idzie streszczenie na strone poczatkowa
 \begin{abstract}
-    % TODO
+    We define $k$-relabel queries 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
+    queries can be performed in constant time after preprocessing the input tree
+    in linear time. Along the way, we show an algorithm for handling queries 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 the same time complexities. Our approach is much simpler in presentation
+    than a previously known solution due to Colcombet.
 \end{abstract}
 
 \tableofcontents