% dodaj opcję [licencjacka] dla pracy licencjackiej
% dodaj opcję [en] dla wersji angielskiej (mogą być obie: [licencjacka,en])
\documentclass[en]{pracamgr}

% Dane magistranta:
\autor{Marcin Chrzanowski}{370754}

\title{MSO Query Answering on Trees}
\titlepl{Odpowiadanie na zapytania MSO na drzewach}
\kierunek{Computer Science}

% Praca wykonana pod kierunkiem:
% (podać tytuł/stopień imię i nazwisko opiekuna
% Instytut
% ew. Wydział ew. Uczelnia (jeżeli nie MIM UW))
\opiekun{dr hab. Szymon Toruńczyk\\
  Institute of Informatics\\
  }

% miesiąc i~rok:
\date{August 2021}

%Podać dziedzinę wg klasyfikacji Socrates-Erasmus:
\dziedzina{
%11.0 Matematyka, Informatyka:\\
%11.1 Matematyka\\
% 11.2 Statystyka\\
11.3 Informatyka\\
%11.4 Sztuczna inteligencja\\
%11.5 Nauki aktuarialne\\
%11.9 Inne nauki matematyczne i informatyczne
}

%Klasyfikacja tematyczna wedlug AMS (matematyka) lub ACM (informatyka)
\klasyfikacja{% TODO
  D. Software\\
  D.127. Blabalgorithms\\
  D.127.6. Numerical blabalysis}

% Słowa kluczowe:
\keywords{MSO, query answering, trees, finite state automata, tree automata}

% Tu jest dobre miejsce na Twoje własne makra i~środowiska:
\newtheorem{defi}{Definicja}[section]

% koniec definicji

\begin{document}
\maketitle

%tu idzie streszczenie na strone poczatkowa
\begin{abstract}
    % TODO
\end{abstract}

\tableofcontents
%\listoffigures
%\listoftables

\chapter*{Introduction}
\addcontentsline{toc}{chapter}{Introduction}

\chapter{Preliminaries}\label{r:pojecia}

% \begin{quote}
  % Blaba, który jest blaba, nie jest prawdziwym blaba.

% \raggedleft\slshape tłum. z~chińskiego Robert Blarbarucki
% \end{quote}

\section{Definitions}

\chapter{Branch Infix Regular Queries}\label{r:branchinfix}

\section{Word infix regular queries}

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 afterwords is able to
answer in time $O(1)$ questions of the form ``Is the infix $w[i, j]$ accepted by
$A$?''. We present the full construction as we will be generalizing its
internals for the tree case.

Suppose $A$ is deterministic. We begin by replacing each letter of $w$ with the
set of states of $A$, $Q$.

Each letter $a$ of $w$ defines an injective function on $Q$, and we draw these
functions as directed edges between successive copies of $Q$. For example, if
$A$ in state $q$, reading $a$, would move to state $q'$, then, for any copy of
$Q$ corresponding to an instance of $a$ in the original word, there will be an
edge from $q$ there to $q'$ in the successive copy of $Q$.

Now we will color the vertices of the graph we just constructed with the colors
$1, 2, \ldots, |Q|$ in such a way that

\begin{enumerate}
    \item every copy of $Q$ has one vertex of each of the $|Q|$ colors;
    \item when a vertex of color $i$ has an edge to a vertex of color $j$ in a
        successive copy of $Q$, then $i \geq j$.
\end{enumerate}

The second point basically means that we will be trying to draw single-color
paths, but when paths need to join, it is the higher-colored path that gets cut
off.

The construction is as follows:

\begin{enumerate}
    \item Color an arbitrary vertex of the first copy of $Q$ with the color $1$.
    \item Follow the deterministic edges to the end of the word, coloring all
        vertices along this path with $1$.
    \item Now color another uncolored vertex of the first copy of $Q$ with the
        color $2$.
    \item Try following edges as far as possible, coloring all vertices with
        $2$.
    \item If your run into an already colored vertex, pick an arbitrary
        uncolored vertex in this copy of $Q$ to color with $2$ and continue from
        here.
    \item Repeat steps 3.-5. for each successive color up to $|Q|$.
\end{enumerate}

Additionally, in each vertex, we store the index of the next copy of $Q$ in
which the path of this vertex's color is broken by a lower color.

\section{Least Common Ancestor via Range Minimum Query}

\section{Highest Black Descendant on Path}

We can now reduce the problem to the following:

\emph{Given}: a tree $T$ with distinguished black vertices.

\emph{Queries}: given a vertex $x$, its descendant $y$, find the node $z$ that
is the highest black node on the path between $x$ and $y$.

We will build an index structure, constructible in linear time, that allows us
to handle such queries in constant time. The structure is heavily inspired by
Bender and Farach-Colton's presentation of an algorithm originally attributed to
Berkman and Vishkin for computing LCA queries.

\subsection{High level overview}

\section{Generalizing words to trees}

\chapter{Conclusions}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% coding: latin-2
%%% End: