From d66b548492085b87869048adedb2417ed537daca Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Thu, 5 Aug 2021 21:20:19 -0400
Subject: Add first version of abstract

---
 mgr.tex | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

(limited to 'mgr.tex')

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
-- 
cgit v1.2.3

