diff options
| -rw-r--r-- | mgr.tex | 10 |
1 files changed, 9 insertions, 1 deletions
@@ -41,7 +41,15 @@ %tu idzie streszczenie na strone poczatkowa \begin{abstract} - % TODO + We define $k$-relabel 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 constant time 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 Colcombet. \end{abstract} \tableofcontents |