m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex16
1 files changed, 5 insertions, 11 deletions
diff --git a/mgr.tex b/mgr.tex
index 855da63..808555f 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -145,9 +145,9 @@ automata.
% def of MSO
From a logical point of view, the trees we work with can be seen as structures
-over a signature with a single binary relation $E$ and unary relations $U_a$ for each $a \in
-\Sigma$. $E(v, w)$ represents a (directed from parent to child) edge from $v$ to
-$w$. $U_a(v)$ signifies that $v$'s label is $a$.
+over a signature with a single binary relation $E$ and unary relations $U_a$ for
+each $a \in \Sigma$. $E(v, w)$ represents a (directed from parent to child) edge
+from $v$ to $w$. $U_a(v)$ signifies that $v$'s label is $a$.
For convenience, we will also make use of the binary relation $\leq$, with $v
\leq w$ signifying that $v$ is an ancestor of $w$ (with every vertex being an
@@ -246,14 +246,8 @@ which the path of this vertex's color is broken by a lower color.
\section{Generalizing to trees}
-We will now generalize the above construction from regular infix queries on a
-word, to ones on a tree. The exact problem we're solving is
-
-\emph{Given}: a tree $T$ with labels from alphabet $\Sigma$, a deterministic
-finite automaton $A$.
-
-\emph{Queries}: given a vertex $x$ and its descendant $y$, is the word given by
-labels on the path from $x$ to $y$ accepted by $A$?
+We generalize the above construction from regular infix queries on a
+word, to ones on a tree.
We begin with similar path coloring as in the word case, i.e. we replace each
vertex of the tree with a copy of the states of $A$, $Q$. Each labeled node