From 8610a510eb8d691024b3637efb12d18721d669dd Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Sat, 7 Aug 2021 15:07:46 -0400
Subject: Define relabel regular queries on trees

---
 mgr.tex | 31 +++++++++++++++++++++++--------
 1 file changed, 23 insertions(+), 8 deletions(-)

(limited to 'mgr.tex')

diff --git a/mgr.tex b/mgr.tex
index c78dfca..06354d9 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -40,15 +40,17 @@
 
 %tu idzie streszczenie na strone poczatkowa
 \begin{abstract}
-    We define $k$-relabel queries on trees, which, via the known equivalence
+    We define relabel regular queries on trees, which, via the known equivalence
     between tree automata and MSO formulae on trees, happens to be a
     generalization of the MSO query answering problem on trees. We show these
-    queries can be performed in constant time after preprocessing the input tree
-    in linear time. Along the way, we show an algorithm for handling queries of
-    the form ``Does the infix of a tree branch between nodes $x$ and $y$ belong
-    to the regular language $L$'' (for a previously fixed regular language $L$)
-    in the same time complexities. Our approach is much simpler in presentation
-    than a previously known solution due to Colcombet.
+    queries can be performed in linear time with respect to query size (constant
+    time in the case of MSO formulae with only first-order free variables) after
+    preprocessing the input tree in linear time. Along the way, we show an
+    algorithm for handling queries of the form ``Does the infix of a tree branch
+    between nodes $x$ and $y$ belong to the regular language $L$'' (for a
+    previously fixed regular language $L$) in the same time complexities. Our
+    approach is much simpler in presentation than a previously known solution
+    due to Colcombet.
 \end{abstract}
 
 \tableofcontents
@@ -69,6 +71,19 @@
     $\vec{X}$? In other words, does $T \models \varphi(\vec{W})$?
 }
 
+\queryproblem[%
+    a deterministic bottom-up tree automaton $A$ over ranked alphabet $\Sigma$.
+]{%
+    Relabel Regular Queries on Trees
+}{%
+    a tree $T$ labeled with $\Sigma$.
+}{%
+    given $m$ relabelings $v_1 \mapsto a_1, \ldots, v_m \mapsto a_m$, where
+    $v_i$ are vertices of $T$ and $a_i$ are elements of $\Sigma$, what state
+    does $A$ arrive  at in the root of $T'$, where $T'$ is $T$ with each $v_i$'s
+    label modified to the corresponding $a_i$.
+}
+
 \chapter{Preliminaries}\label{r:pojecia}
 
 % \begin{quote}
@@ -253,7 +268,7 @@ Now when given a query $x$, $y$, we:
         answer to our query.
 \end{enumerate}
 
-\chapter{$k$-relabel Queries on Trees}
+\chapter{Relabel Regular Queries on Trees}
 h
 
 \chapter{Conclusions}
-- 
cgit v1.2.3