diff options
| -rw-r--r-- | definitions.sty | 2 | ||||
| -rw-r--r-- | mgr.tex | 78 |
2 files changed, 78 insertions, 2 deletions
diff --git a/definitions.sty b/definitions.sty index cbe36f2..1105fb3 100644 --- a/definitions.sty +++ b/definitions.sty @@ -18,3 +18,5 @@ \newcommand{\qpoptimal}{\qptime{$O(n)$}{$O(1)$}} \newcommand{\definedterm}[1]{\emph{#1}} + +\newcommand{\mathlca}{\mathit{LCA}} @@ -453,8 +453,82 @@ jump takes constant time, and the number of jumps is bounded $|Q|$ since we can only jump to a lower color. Thus we can answer branch infix regular queries in constant time. -\chapter{Relabel Regular Queries on Trees} -h +\chapter{MSO Query Answering on Trees} + +\section{Relabel Regular Queries on Trees} + +Fix a tree automaton $A$ and take a $\Sigma$-labeled binary tree $T$. + +We'll preprocess the tree in such a way that when given a relabel query, we'll +be able to partition the tree into linearly (with respect to the query's size) +many parts, then, in a bottom-up fashion, compute the state in the root of each +part in the relabeled tree. The computation for each part will take constant +time. + +\subsection{LCA partition} + +Consider a set of tree vertices $W$. We'll say that $W$ is \definedterm{LCA +closed} if for every pair of vertices $v, w \in W$, it is the case that +$\mathlca(v, w) \in W$ (note that one of $v$ or $w$ might be their LCA). We also +require that the tree's root is in $W$ (just to ensure the partition we define +next covers the whole tree). + +The \definedterm{subtree of $v$} is $v$ along with all its descendants. +We also consider subtrees with holes: the \definedterm{subtree of $v$ with hole +$w$} is the subtree of $v$ minus the subtree of $w$. + +For an LCA closed set $W$ in tree $T$, we define the \definedterm{LCA partition with +respect to $W$} to be a partition of $T$'s vertices into subtrees, subtrees with +holes, and individual vertices created according to the following rules: + +\begin{enumerate} + \item If $v \in W$ is a maximal element with respect to the ancestor + relation $<$ (i.e. there are no other elements of $W$ in the subtree of + $v$), then the subtree of $v$ is a part of the partition. + \item If $v \in W$ has descendants that are in $W$ only in its left subtree, + let $w$ be the highest such descendant (there is a unique highest + descendant because $W$ is LCA closed). The subtree of $v$ with hole $w$ + is a part of the partition. + \item Symmetrically if $v \in W$ only has descendants that are in $W$ in its + right subtree. + \item If $v \in W$ has descendants that are in $W$ in both its subtrees, let + $v_l$ and $v_r$ be $v$'s left and right child, respectively. Treat $v_l$ + and $v_r$ as if they were in $W$ for the purposes of defining the + partition. Put $v$ into a singleton part on its own. +\end{enumerate} + +Note that in the last rule, both $v_l$ and $v_r$ will either themselves be +elements of $W$ or will have descendants in $W$ in only one of their subtrees. +Indeed, if for example $v_l$ wasn't in $W$ but it had descendants from $W$ in +both its subtrees, then $W$ wouldn't have been LCA closed. + +Thus the partition covers the entire tree with $O(|W|)$ parts. + +If $W$ is not LCA closed, we will call the LCA partition with respect to $W$ +simply the partition with respect to $W$'s LCA closure. + +\subsection{Computing the LCA closure} + +The LCA closure of a set of $m$ vertices $W$ can be computed in time $O(m \log +m)$ after linear preprocessing of the tree $T$. In the preprocessing step, in +addition to preprocessing for LCA queries, we will additionally assign each +vertex $v$ its in-order number, $IN[v]$. + +Now to compute the closure of $W$, we first sort the vertices in $W$ with +respect to their in-order numbers, so we end up with a list $v_1, \ldots, v_m$ +of vertices such that $IN[v_1] < \ldots < IN[v_m]$. + +Lemma: if $IN[u] < IN[v] < IN[w]$, then $\mathlca(u, w)$ is equal to either +$\mathlca(u, v)$ or $\mathlca(v, w)$. + +This may be proved by a simple case analysis. + +By the above lemma, once $W$ has been sorted by in-order numbers, we can +complete our computation in time $O(m)$. It is enough to walk through the list +and issue LCA queries about neighboring pairs. + +\section{Computing root states of parts} + \chapter{Conclusions} |