diff options
Diffstat (limited to 'mgr.tex')
| -rw-r--r-- | mgr.tex | 25 |
1 files changed, 22 insertions, 3 deletions
@@ -4,6 +4,7 @@ \usepackage{definitions} \usepackage[backend=biber]{biblatex} +\usepackage{graphicx} \addbibresource{mgr.bib} \usepackage{amsmath} @@ -431,12 +432,30 @@ The construction is as follows: \item Repeat steps 3.-5. for each successive color up to $|Q|$. \end{enumerate} -Additionally, for each vertex $i.q$, 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. Put this +\begin{figure} + \centering + \def\svgwidth{\columnwidth} + \input{word.pdf_tex} + \caption{ + The data structure for infix regular queries over word $abaacbc$ and a + simple automaton with 4 states. As shown by the color blotches below the + graph, red is color 1, with the highest priority, green is color 2 with + the next priority, pink is color 3, blue is color 4, with the lowest + priority. + The information from $\breaktable$ is not shown in the figure, but it + amounts to a pointer from each vertex to the last vertex on its + connected single color component. + }\label{word-figure} +\end{figure} + +Additionally, for each vertex $i.q$, 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. Put this information in table $\breaktable$. For example, if $i.q$ is colored with color $c$, and when following the deterministic path from $i.q$, all encountered vertices are colored $c$ until $j.q'$ which is colored $c'$, then we set -$\breaktable[i.q] = j - 1$. +$\breaktable[i.q] = j - 1$. See Figure \ref{word-figure} for a visual +representation of the data structure described for an example word and +automaton. We can compute $\breaktable$ in linear time with a single backwards pass through the colored graph. |