m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex16
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