diff options
Diffstat (limited to 'mgr.tex')
| -rw-r--r-- | mgr.tex | 16 |
1 files changed, 5 insertions, 11 deletions
@@ -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 |