Fix time complexity in abstract

1 files changed, 8 insertions, 8 deletions

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