diff options
| -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 |