diff options
Diffstat (limited to 'mgr.tex')
-rw-r--r-- | mgr.tex | 26 |
1 files changed, 26 insertions, 0 deletions
@@ -5,6 +5,7 @@ \usepackage{definitions} \usepackage[backend=biber]{biblatex} \usepackage{graphicx} +\usepackage{subcaption} \addbibresource{mgr.bib} \usepackage{amsmath} @@ -543,6 +544,31 @@ This process will again lead to a coloring with the desired properties that child copy of $Q$, then $c \geq c'$. \end{enumerate} +\begin{figure} + \centering + \def\svgwidth{\columnwidth} + \begin{subfigure}{0.3\linewidth} + \input{tree.pdf_tex} + \caption{The original tree $T$} + \end{subfigure} + \def\svgwidth{\columnwidth} + \begin{subfigure}{0.4\linewidth} + \input{tree-graph.pdf_tex} + \caption{The colored graph} + \end{subfigure} + \caption{ + On the left, a sample labeled tree. On the right, the colored graph we + create for the purposes of answering branch infix regular questions for + this tree and a simple three state automaton. Note how the copies of the + automaton's states are arranged in the same as shape as $T$, with an + additional new root copy. The letters of the original tree fit in the + spaces between copies of $Q$, inducing the edges between them. + }\label{tree-figure} +\end{figure} + +See Figure \ref{tree-figure} for how the colored graph is constructed for an +example tree. + Now let's consider how we could answer the question ``is the branch infix from $x$ down to $y$ in $L$?''. Here we can't proceed exactly as in the word case. We don't have a $\breaktable$ table since a vertex in an internal node can have |