m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
path: root/mgr.tex
diff options
context:
space:
mode:
Diffstat (limited to 'mgr.tex')
-rw-r--r--mgr.tex26
1 files changed, 26 insertions, 0 deletions
diff --git a/mgr.tex b/mgr.tex
index ce27d02..a89eb4b 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -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