diff options
| -rw-r--r-- | mgr.tex | 2 |
1 files changed, 1 insertions, 1 deletions
@@ -788,7 +788,7 @@ interpreted as a bit vector signifying which unary relations $U_X$ a vertex is assigned to. By combining the above reductions, we can solve MSO query answering on trees by -solving the relabel regular qustions problem on trees. Indeed, fix a formula +solving the relabel regular qeustions problem on trees. Indeed, fix a formula $\varphi(\vec{X})$ and take a tree $T$. Derive automaton $A$ and tree $T'$ as above. Label each vertex of $T'$ with $0\ldots0$ (signifying that none of its vertices have yet been assigned to any of the variables in $\vec{X}$). |