m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex26
-rw-r--r--tree-graph.pdfbin0 -> 7876 bytes
-rw-r--r--tree-graph.pdf_tex58
-rw-r--r--tree.pdfbin0 -> 4592 bytes
-rw-r--r--tree.pdf_tex58
5 files changed, 142 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
diff --git a/tree-graph.pdf b/tree-graph.pdf
new file mode 100644
index 0000000..d0723c8
--- /dev/null
+++ b/tree-graph.pdf
Binary files differ
diff --git a/tree-graph.pdf_tex b/tree-graph.pdf_tex
new file mode 100644
index 0000000..998c358
--- /dev/null
+++ b/tree-graph.pdf_tex
@@ -0,0 +1,58 @@
+%% Creator: Inkscape 1.1.1 (3bf5ae0d25, 2021-09-20, custom), www.inkscape.org
+%% PDF/EPS/PS + LaTeX output extension by Johan Engelen, 2010
+%% Accompanies image file 'tree-graph.pdf' (pdf, eps, ps)
+%%
+%% To include the image in your LaTeX document, write
+%% \input{<filename>.pdf_tex}
+%% instead of
+%% \includegraphics{<filename>.pdf}
+%% To scale the image, write
+%% \def\svgwidth{<desired width>}
+%% \input{<filename>.pdf_tex}
+%% instead of
+%% \includegraphics[width=<desired width>]{<filename>.pdf}
+%%
+%% Images with a different path to the parent latex file can
+%% be accessed with the `import' package (which may need to be
+%% installed) using
+%% \usepackage{import}
+%% in the preamble, and then including the image with
+%% \import{<path to file>}{<filename>.pdf_tex}
+%% Alternatively, one can specify
+%% \graphicspath{{<path to file>/}}
+%%
+%% For more information, please see info/svg-inkscape on CTAN:
+%% http://tug.ctan.org/tex-archive/info/svg-inkscape
+%%
+\begingroup%
+ \makeatletter%
+ \providecommand\color[2][]{%
+ \errmessage{(Inkscape) Color is used for the text in Inkscape, but the package 'color.sty' is not loaded}%
+ \renewcommand\color[2][]{}%
+ }%
+ \providecommand\transparent[1]{%
+ \errmessage{(Inkscape) Transparency is used (non-zero) for the text in Inkscape, but the package 'transparent.sty' is not loaded}%
+ \renewcommand\transparent[1]{}%
+ }%
+ \providecommand\rotatebox[2]{#2}%
+ \newcommand*\fsize{\dimexpr\f@size pt\relax}%
+ \newcommand*\lineheight[1]{\fontsize{\fsize}{#1\fsize}\selectfont}%
+ \ifx\svgwidth\undefined%
+ \setlength{\unitlength}{1372.34923535bp}%
+ \ifx\svgscale\undefined%
+ \relax%
+ \else%
+ \setlength{\unitlength}{\unitlength * \real{\svgscale}}%
+ \fi%
+ \else%
+ \setlength{\unitlength}{\svgwidth}%
+ \fi%
+ \global\let\svgwidth\undefined%
+ \global\let\svgscale\undefined%
+ \makeatother%
+ \begin{picture}(1,0.90071325)%
+ \lineheight{1}%
+ \setlength\tabcolsep{0pt}%
+ \put(0,0){\includegraphics[width=\unitlength,page=1]{tree-graph.pdf}}%
+ \end{picture}%
+\endgroup%
diff --git a/tree.pdf b/tree.pdf
new file mode 100644
index 0000000..d4da0aa
--- /dev/null
+++ b/tree.pdf
Binary files differ
diff --git a/tree.pdf_tex b/tree.pdf_tex
new file mode 100644
index 0000000..36d98d1
--- /dev/null
+++ b/tree.pdf_tex
@@ -0,0 +1,58 @@
+%% Creator: Inkscape 1.1.1 (3bf5ae0d25, 2021-09-20, custom), www.inkscape.org
+%% PDF/EPS/PS + LaTeX output extension by Johan Engelen, 2010
+%% Accompanies image file 'tree.pdf' (pdf, eps, ps)
+%%
+%% To include the image in your LaTeX document, write
+%% \input{<filename>.pdf_tex}
+%% instead of
+%% \includegraphics{<filename>.pdf}
+%% To scale the image, write
+%% \def\svgwidth{<desired width>}
+%% \input{<filename>.pdf_tex}
+%% instead of
+%% \includegraphics[width=<desired width>]{<filename>.pdf}
+%%
+%% Images with a different path to the parent latex file can
+%% be accessed with the `import' package (which may need to be
+%% installed) using
+%% \usepackage{import}
+%% in the preamble, and then including the image with
+%% \import{<path to file>}{<filename>.pdf_tex}
+%% Alternatively, one can specify
+%% \graphicspath{{<path to file>/}}
+%%
+%% For more information, please see info/svg-inkscape on CTAN:
+%% http://tug.ctan.org/tex-archive/info/svg-inkscape
+%%
+\begingroup%
+ \makeatletter%
+ \providecommand\color[2][]{%
+ \errmessage{(Inkscape) Color is used for the text in Inkscape, but the package 'color.sty' is not loaded}%
+ \renewcommand\color[2][]{}%
+ }%
+ \providecommand\transparent[1]{%
+ \errmessage{(Inkscape) Transparency is used (non-zero) for the text in Inkscape, but the package 'transparent.sty' is not loaded}%
+ \renewcommand\transparent[1]{}%
+ }%
+ \providecommand\rotatebox[2]{#2}%
+ \newcommand*\fsize{\dimexpr\f@size pt\relax}%
+ \newcommand*\lineheight[1]{\fontsize{\fsize}{#1\fsize}\selectfont}%
+ \ifx\svgwidth\undefined%
+ \setlength{\unitlength}{567.89071872bp}%
+ \ifx\svgscale\undefined%
+ \relax%
+ \else%
+ \setlength{\unitlength}{\unitlength * \real{\svgscale}}%
+ \fi%
+ \else%
+ \setlength{\unitlength}{\svgwidth}%
+ \fi%
+ \global\let\svgwidth\undefined%
+ \global\let\svgscale\undefined%
+ \makeatother%
+ \begin{picture}(1,1.02815594)%
+ \lineheight{1}%
+ \setlength\tabcolsep{0pt}%
+ \put(0,0){\includegraphics[width=\unitlength,page=1]{tree.pdf}}%
+ \end{picture}%
+\endgroup%