From d66b548492085b87869048adedb2417ed537daca Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Thu, 5 Aug 2021 21:20:19 -0400 Subject: Add first version of abstract --- mgr.tex | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-) (limited to 'mgr.tex') diff --git a/mgr.tex b/mgr.tex index 1a727ed..37bc034 100644 --- a/mgr.tex +++ b/mgr.tex @@ -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 -- cgit v1.2.3