From 7bb424b859ff58d360aa9ba7578edc8caebf69fe Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Fri, 13 Aug 2021 10:44:19 -0400
Subject: Fix time complexity in abstract

---
 mgr.tex | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

(limited to 'mgr.tex')

diff --git a/mgr.tex b/mgr.tex
index 919a9b8..cd44d87 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -46,14 +46,14 @@
     We define relabel regular 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 linear time with respect to query size (constant
-    time in the case of MSO formulae with only first-order free variables) 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 \textcite{colcombet}.
+    queries can be performed in time $O(m \log(m))$ with respect to query size
+    (constant time in the case of MSO formulae with only first-order free
+    variables) 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 constant time after linear
+    preprocessing.  Our approach is much simpler in presentation than a
+    previously known solution due to \textcite{colcombet}.
 \end{abstract}
 
 \tableofcontents
-- 
cgit v1.2.3

