diff options
| -rw-r--r-- | mgr.tex | 31 |
1 files changed, 23 insertions, 8 deletions
@@ -40,15 +40,17 @@ %tu idzie streszczenie na strone poczatkowa \begin{abstract} - We define $k$-relabel queries on trees, which, via the known equivalence + 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 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. + 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 Colcombet. \end{abstract} \tableofcontents @@ -69,6 +71,19 @@ $\vec{X}$? In other words, does $T \models \varphi(\vec{W})$? } +\queryproblem[% + a deterministic bottom-up tree automaton $A$ over ranked alphabet $\Sigma$. +]{% + Relabel Regular Queries on Trees +}{% + a tree $T$ labeled with $\Sigma$. +}{% + given $m$ relabelings $v_1 \mapsto a_1, \ldots, v_m \mapsto a_m$, where + $v_i$ are vertices of $T$ and $a_i$ are elements of $\Sigma$, what state + does $A$ arrive at in the root of $T'$, where $T'$ is $T$ with each $v_i$'s + label modified to the corresponding $a_i$. +} + \chapter{Preliminaries}\label{r:pojecia} % \begin{quote} @@ -253,7 +268,7 @@ Now when given a query $x$, $y$, we: answer to our query. \end{enumerate} -\chapter{$k$-relabel Queries on Trees} +\chapter{Relabel Regular Queries on Trees} h \chapter{Conclusions} |