thesis update

[bsc-thesis1415.git] / thesis2 / 2.methods.tex

diff --git a/thesis2/2.methods.tex b/thesis2/2.methods.tex
index a0afd71..9df1941 100644 (file)
--- a/thesis2/2.methods.tex
+++ b/thesis2/2.methods.tex
@@ -47,6 +47,25 @@ converted to a graph representation.
 
 \subsection{Directed acyclic graphs(DAG)}
 Directed acyclic graphs are a special kind of graph that is used to store big
-sets of words and has a linear #TODO, CITE THIS# access times.
+sets of words and has a complexity of $\mathcal{O}(L)$, meaning the length of
+the word you are searching. Figure~\ref{fig:f21} shows a DAG that accepts the
+words \textit{aa} and \textit{ab}. Final states are marked with a double circle
+and intermediate states are marked with a single circle.
 
+\begin{figure}[H]
+       \caption{Sample DAG}
+       \label{fig:f21}
+       \centering
+       \digraph[]{graph2}{
+               rankdir=LR;
+               1, 2 [shape="circle"];
+               3, 4 [shape="doublecircle"];
+               1 -> 2 [label="a"];
+               2 -> 3 [label="a"];
+               2 -> 4 [label="b"];
+       }
+\end{figure}
 
+Using the algorithm described by Hopcroft et al\cite{Hopcroft1971} the
+nodelists are converted into minimal directed acyclic graphs with a low
+complexity($\mathcal{O}(N\log{N})$).