diff options
author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-08-13 10:44:19 -0400 |
---|---|---|
committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-08-13 10:44:19 -0400 |
commit | 7bb424b859ff58d360aa9ba7578edc8caebf69fe (patch) | |
tree | 5c45ca66f584a470cafd2f7c5bba722af8f0efe4 | |
parent | c4965bcb7d623e0b105469e31e48c4c354e07bff (diff) |
Fix time complexity in abstract
-rw-r--r-- | mgr.tex | 16 |
1 files changed, 8 insertions, 8 deletions
@@ -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 |