m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-08-13 10:44:19 -0400
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-08-13 10:44:19 -0400
commit7bb424b859ff58d360aa9ba7578edc8caebf69fe (patch)
tree5c45ca66f584a470cafd2f7c5bba722af8f0efe4
parentc4965bcb7d623e0b105469e31e48c4c354e07bff (diff)
Fix time complexity in abstract
-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