diff options
| -rw-r--r-- | mgr.tex | 43 |
1 files changed, 42 insertions, 1 deletions
@@ -56,6 +56,19 @@ \chapter{Introduction} % \addcontentsline{toc}{chapter}{Introduction} +\queryproblem[% + an MSO formula $\varphi(\vec{X})$ over trees with $k$ free + second-order variables. +]{% + MSO Query Answering on Trees +}{% + a tree $T$. +}{% + given a $k$-tuple of subsets of $T$'s vertices $\vec{W} + \in \mathcal{P}(V(T))^{k}$, is $\vec{W}$ a satisfying assignment to + $\vec{X}$? In other words, does $T \models \varphi(\vec{W})$? +} + \chapter{Preliminaries}\label{r:pojecia} % \begin{quote} @@ -75,14 +88,42 @@ c d \section{Known algorithms we will use} \subsection{Least Common Ancestor} -e + +\queryproblem{% + Least Common Ancestor (LCA) +}{% + a tree $T$. +}{% + given vertices $x$ and $y$, find the vertex $z$ that's an ancestor of both + $x$ and $y$, and is their lowest (i.e. furthest from the root) common + ancestor. +} + \subsection{Range Minimum Query} f \chapter{Branch Infix Regular Queries}\label{r:branchinfix} +\queryproblem[% + regular language $L$ over alphabet $\Sigma$. +]{Branch Infix Regular Queries}{% + a $\Sigma$-labeled tree $T$. +}{% + given a vertex $x$ and its descendant $y$, does the word given by labels on + the path from $x$ to $y$ belong to $L$? +} + \section{Word infix regular queries} +\queryproblem[% + regular language $L$ over alphabet $\Sigma$. +]{Word Infix Regular Queries}{% + a word $w \in \Sigma^*$. +}{% + given indices $i$ and $j$ with $1 \leq i < j \leq |w|$, does the infix $w[i, + j]$ belong to $L$? +} + There is a simple and well-known data structure that, given a fixed automaton $A$, preprocesses an input word $w$ in time $O(n)$, and afterwards is able to answer in time $O(1)$ questions of the form ``Is the infix $w[i, j]$ accepted by |