diff options
| -rw-r--r-- | mgr.tex | 26 | ||||
| -rw-r--r-- | tree-graph.pdf | bin | 0 -> 7876 bytes | |||
| -rw-r--r-- | tree-graph.pdf_tex | 58 | ||||
| -rw-r--r-- | tree.pdf | bin | 0 -> 4592 bytes | |||
| -rw-r--r-- | tree.pdf_tex | 58 |
5 files changed, 142 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 diff --git a/tree-graph.pdf b/tree-graph.pdf Binary files differnew file mode 100644 index 0000000..d0723c8 --- /dev/null +++ b/tree-graph.pdf 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 Binary files differnew file mode 100644 index 0000000..d4da0aa --- /dev/null +++ b/tree.pdf 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% |