From 4ddbff9fecc363844e8ce26d5851ebde9a19a902 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Sat, 7 Aug 2021 20:20:59 -0400 Subject: Small fixes --- mgr.tex | 16 +++++----------- 1 file 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 -- cgit v1.2.3