From f92048908c9d54dd1df528c47c5f6b4e00082e5e Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Thu, 9 Dec 2021 16:42:04 +0100 Subject: Queries to questions --- mgr.tex | 281 +++++++++++++++++++++++++++++++++------------------------------- 1 file changed, 144 insertions(+), 137 deletions(-) diff --git a/mgr.tex b/mgr.tex index 3556e3c..3ad657e 100644 --- a/mgr.tex +++ b/mgr.tex @@ -39,23 +39,23 @@ D.127. Blabalgorithms\\ D.127.6. Numerical blabalysis} -\keywords{MSO, query answering, tree automata, RMQ} +\keywords{MSO, query answering, tree automata} \begin{document} \maketitle \begin{abstract} - We define relabel regular queries on trees, which, via the known equivalence - between tree automata and MSO formulae on trees, happens to be a + We define relabel regular questions 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 time $O(m \log(m))$ with respect to query size - (constant time in the case of MSO formulae with only first-order free + questions can be answered in time $O(m \log(m))$ with respect to question + 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$'' + we show an algorithm for answering questions 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 constant time after linear - preprocessing. Our approach is much simpler in presentation than a - previously known solution due to \textcite{colcombet}. + preprocessing. Our approach is much simpler in presentation than if using + deterministic factorization forests due to \textcite{colcombet}. \end{abstract} \tableofcontents @@ -135,7 +135,7 @@ the following problem about tree automata, which we solve in Chapter \queryproblem[% a deterministic bottom-up tree automaton $A$ over ranked alphabet $\Sigma$. ]{% - \label{relabel-regular-queries} Relabel Regular Queries on Trees + \label{relabel-regular-queries} Relabel Regular Questions on Trees }{% a tree $T$ labeled with $\Sigma$. }{% @@ -166,9 +166,9 @@ factorization forests due to \textcite{colcombet} rather than Bagan's intricate indexing structure. Colcombet's factorization could likely be used to solve the problem of branch -infix regular queries, which we introduce as a subproblem of MSO query answering -in Chapter \ref{branchinfix}. However, Colcombet's result depends on fairly deep -and complex applications of semigroup theory. We present a much more +infix regular questions, which we introduce as a subproblem of MSO query +answering in Chapter \ref{branchinfix}. However, Colcombet's result depends on +fairly deep and complex applications of semigroup theory. We present a much more straightforward algorithmic approach. \section{Organization} @@ -307,34 +307,36 @@ automaton, there is a corresponding MSO formula), however we will use only the MSO to automata direction in this work. See for example Bojańczyk's text \cite{bojanczyktoolbox} for a proof of both directions. -\section{Query answering problems}\label{query-answering-problems} +\section{Question answering problems}\label{query-answering-problems} Consider a computational problem whose inputs are of the form $(S, q) \in \mathcal{S} \times \mathcal{Q}$ for some set of \definedterm{structures} -$\mathcal{S}$ and some set of \definedterm{queries} $\mathcal{Q}$. This induces -a \definedterm{query answering problem} which is divided into two phases: +$\mathcal{S}$ and some set of \definedterm{questions} $\mathcal{Q}$. This +induces a \definedterm{question answering problem} which is divided into two +phases: \begin{description} \item[preprocessing] An input structure $S \in \mathcal{S}$ is given and a \definedterm{preprocessing algorithm} outputs a data structure $S'$. - \item[queries] $S'$ is used to handle queries $q_1, \ldots$ from + \item[questions] $S'$ is used to handle questions $q_1, \ldots$ from $\mathcal{Q}$. \end{description} We are interested in the time complexities of both phases. We use the following -notation for algorithms that have both a preprocessing and query phase: If +notation for algorithms that have both a preprocessing and question phase: if it takes $f(n)$ time to complete the preprocessing step for an input of size -$n$, and $g(n, m)$ time to then handle a query of size $m$, we say the algorithm -has time complexity \qptime{$f(n)$}{$g(n, m)$}. +$n$, and $g(n, m)$ time to then handle a question of size $m$, we say the +algorithm has time complexity \qptime{$f(n)$}{$g(n, m)$}. -We turn to a discussion of several query problems with known solutions, both to -serve as examples and because we will be using them in our algorithm. +We turn to a discussion of several question answering problems with known +solutions, both to serve as examples and because we will be using them in our +algorithm. \subsection{Lowest Common Ancestor} \queryproblem{% - Lowest Common Ancestor (LCA) Queries + Lowest Common Ancestor (LCA) }{% a tree $T$. }{% @@ -365,14 +367,14 @@ equivalence between the LCA and RMQ problems. Their method is as follows. First they show that a special case of the RMQ problem, $\pm1$ RMQ, can be solved in \qpoptimal. This restriction of the problem -is enough to handle LCA queries. Then, for the general RMQ case, a Cartesian +is enough to handle LCA questions. Then, for the general RMQ case, a Cartesian tree\footnote{A Cartesian tree of an array is a binary tree with the array's minimum element in its root, the root's children being Cartesian trees of the left and right subarrays around the minimal element. It can be constructed in -linear time.} of the array is built, and LCA queries on this tree correspond to -range minimum queries on the array. +linear time.} of the array is built, and LCA questions on this tree correspond +to range minimum queries on the array. -\subsection{Word infix regular queries}\label{wordinfix} +\subsection{Word infix regular questions}\label{wordinfix} We now turn to a problem about regular languages. Note that the regular language is fixed, i.e. we treat the size of its representation (e.g. the size of an @@ -382,7 +384,7 @@ automaton we ``don't care'' about the exponential cost of determinizing it. \queryproblem[% regular language $L$ over alphabet $\Sigma$, given by DFA $A$. -]{Word Infix Regular Queries}{% +]{Word Infix Regular Questions}{% a word $w \in \Sigma^*$. }{% given indices $i$ and $j$ with $1 \leq i < j \leq |w|$, does the infix $w[i, @@ -405,7 +407,7 @@ state $q$, reading $a$, would move to state $q'$, then there will be an edge from $i.q$ to $(i+1).q'$. Note that by determinism, each vertex has exactly one outgoing edge (except for -vertices in the last copy of $Q$ which have no outgoing edges). +vertices in the last copy of $Q$ which have no outgoing edges at all). Now we will color the vertices of the graph we just constructed with the colors $1, 2, \ldots, |Q|$ in such a way that @@ -442,13 +444,13 @@ The construction is as follows: \def\svgwidth{\columnwidth} \input{word.pdf_tex} \caption{ - The data structure for infix regular queries over word $abaacbc$ and a + The data structure for infix regular questions over word $abaacbc$ and a simple automaton with 4 states. As shown by the color blotches below the graph, red is color 1, with the highest priority, green is color 2 with the next priority, pink is color 3, blue is color 4, with the lowest priority. The information from $\breaktable$ is not shown in the figure, but it - amounts to a pointer from each vertex to the last vertex on its + amounts to a pointer from each vertex to the rightmost vertex on its connected single color component. }\label{word-figure} \end{figure} @@ -465,10 +467,11 @@ automaton. We can compute $\breaktable$ in linear time with a single backwards pass through the colored graph. -\textbf{answering queries} Consider a query ``does $w[i, j] \in L$''. We claim that using our colored graph -and the table $\breaktable$ we can, in constant time, conclude in what state the -automaton $A$ will end up in on the $j$th position of $w$ if it had started in -its initial state on the $i$th position. +\textbf{answering questions} Consider a question ``does $w[i, j] \in L$''. We +claim that using our colored graph and the table $\breaktable$ we can, in +constant time, conclude in what state the automaton $A$ will end up in on the +$j$th position of $w$ if it had started in its initial state on the $i$th +position. First, look at vertex $i.q_0$, which is the vertex of $A$'s initial state in the $i$th copy of $Q$ and note its color $c$. Now we want to answer the following @@ -482,24 +485,24 @@ answer YES, if not, answer NO. If $k < j$, then jump to the $k$th copy of $Q$ and consider the vertex $k.q$, the unique vertex here colored $c$. From $k.q$, follow its single outgoing edge to $(k+1).q'$, which will be colored with color $c' < c$. Continue as we did -before, by looking at $k' := \breaktable[(k+1).q']$, comparing it to $j$, and either -halting if $k' \geq j$, or jumping again otherwise. Because with each jump we -move to a color strictly smaller than before, the number of jumps is bounded by -the number of colors, $|Q|$. Thus the query is answered in time constant with -respect to $|w|$. +before, by looking at $k' := \breaktable[(k+1).q']$, comparing it to $j$, and +either halting if $k' \geq j$, or jumping again otherwise. Because with each +jump we move to a color strictly smaller than before, the number of jumps is +bounded by the number of colors, $|Q|$. Thus the question is answered in time +constant with respect to $|w|$. -\chapter{Branch Infix Regular Queries}\label{branchinfix} +\chapter{Branch Infix Regular Questions}\label{branchinfix} -Before solving our main problem, that of MSO queries on trees, we generalize -word infix regular queries (section \ref{wordinfix}) to trees. This will be a -vital step in the MSO queries algorithm, but is an interesting result on its -own. +Before solving our main problem, that of MSO query answering on trees, we +generalize word infix regular questions (Section \ref{wordinfix}) to trees. This +will be a vital step in the MSO query algorithm, but is an interesting result on +its own. -The query problem we will solve is: +The question answering problem we will solve is: \queryproblem[% regular language $L$ over alphabet $\Sigma$. -]{Branch Infix Regular Queries}{% +]{Branch Infix Regular Questions}{% a $\Sigma$-labeled tree $T$. }{% given a vertex $x$ and its descendant $y$, does the word given by labels on @@ -517,11 +520,11 @@ labeled with letter $a$ and having children $y$ and $z$. If $A$ in state $q$, reading letter $a$ goes to $q'$, then there will be edges from $x.q$ to $y.q'$ and $z.q'$. -We also color all vertices with $1, \ldots, |Q|$ in this graph, analogously to -how we did so in the word case: begin by coloring an arbitrary vertex in the -root with $1$, then follow edges downwards, coloring all visited vertices with -$1$. Then begin the same process with the next color, restarting with a -different vertex in a given copy of $Q$ if we run into an already colored +We also color all vertices with colors $1, \ldots, |Q|$ in this graph, +analogously to how we did so in the word case: begin by coloring an arbitrary +vertex in the root with $1$, then follow edges downwards, coloring all visited +vertices with $1$. Then begin the same process with the next color, restarting +with a different vertex in a given copy of $Q$ if we run into an already colored vertex. This process will again lead to a coloring with the desired properties that @@ -532,21 +535,21 @@ This process will again lead to a coloring with the desired properties that child copy of $Q$, then $c \geq c'$. \end{enumerate} -Now let's consider how we could answer a query ``is the branch infix from $x$ -down to $y$ in $L$?''. Here we can't proceed exactly as in the word case. We +Now let's consider how we could answer the question ``is the branch infix from +$x$ down to $y$ in $L$?''. Here we can't proceed exactly as in the word case. We don't have a $\breaktable$ table since a vertex in an internal node can have arbitrarily many points below it where its color is broken by a lower one. -Somehow we need to be able to find such a break point that is ``in the direction -of $y$ from $x$''. +Somehow we need to be able to find such a color break point that is ``in the +direction of $y$ from $x$''. In the next section we formulate this question formally and solve it as a subproblem. \section{Highest Marked Descendant on Path} -We will show that the branch infix problem reduces to the following: +Consider the following question answering problem: -\queryproblem{Highest Marked Descendant on Path Queries}{% +\queryproblem{Highest Marked Descendant on Path Questions}{% a tree $T$ with set $M \subseteq V(T)$ of marked vertices. }{% given a vertex $x$, its descendant $y$, find the node $z \in M$ that @@ -555,12 +558,12 @@ We will show that the branch infix problem reduces to the following: } We will build an index structure, constructible in linear time, that allows us -to handle such queries in constant time. The structure is heavily inspired by -\textcite{bender2000}, where a simple algorithm for computing LCA queries is +to handle such questions in constant time. The structure is heavily inspired by +\textcite{bender2000}, where a simple algorithm for answering LCA questions is presented. -First, we create the array $\posttable$ of length $n$, which is the post-order of -the nodes. +First, we create the array $\posttable$ of length $n$, which is the post-order +of the nodes. Next, we label each node of the tree with its pre-order number. We create the array $\prefixtable$ with the corresponding pre-order labels of the nodes in @@ -607,18 +610,19 @@ vertices $v$, we change $\prefixtable[\indextable[v]]$ to $\infty$ (which can be represented by $n+1$, an integer greater than any node's pre-order label). With $\prefixtable$ modified like this, we observe that now the minimum value of $\prefixtable[\indextable[y], \indextable[x] - 1]$ corresponds exactly to the -answer of our queries -- the highest marked node between $x$ and $y$. +answer of our question -- the highest marked node between $x$ and $y$. -We preprocess $\prefixtable$ for RMQ queries in linear time. +We preprocess $\prefixtable$ for RMQ in linear time. -Now when given a query $x$, $y$, we: +Now when given a question ``what is the highest marked descendant of $x$ in the +direction of $y$'', we: \begin{enumerate} \item Lookup $i := \indextable[y]$ and $j := \indextable[x] - 1$. - \item Perform an RMQ query on $\prefixtable[i, j]$, giving us index $k$ of + \item Perform an RMQ lookup on $\prefixtable[i, j]$, giving us index $k$ of the minimal value in that range. \label{hmd-algo-lookup} \item Lookup the corresponding vertex as $z := \posttable[k]$. This is the - answer to our query. + answer to our question. \end{enumerate} We can detect the siutation of there not being a marked node between $x$ and $y$ @@ -630,44 +634,46 @@ and $k$ will correspond to a marked node that's not on the path from $x$ to $y$ (or some unmarked vertex if there were no marked vertices at all in the range we check). -\section{Solving branch infix regular queries} - -With the above problem solved, we are ready to finish our algorithm for the -branch infix regular query problem. Recall that we have replaced the input tree -$T$'s vertices with copies of $Q$, then connected and colored them in the same -way as in the word case. We additionally remember in each vertex a unique -identifier of the connected component of vertices of the same color that it is -in (call this data $\componenttable[v]$). - -For each color $c$, we will preprocess the above graph for queries that answer -the question ``if we start in a vertex $v$ colored with $c$, which is the first -copy of $Q$ on the path towards the copy of $Q$ that contains $y$?'' by creating -a copy of $T$ in which we mark the vertices where an edge from a $c$ colored -vertex points to a vertex with a lower color. This tree we preprocess for -highest marked descendant on path queries. - -Now query answering can proceed similar to the word case. Given a query ``does -the word on vertices from $x$ down to $y$ belong to $L$?'' look at the vertex -$x.q_0$ and consider its color $c$. In the copy of $Q$ corresponding to $y$ -consider the vertex $y.q$, the unique vertex here of color $c$. If it is in the -same connected component as $x.q_0$ (which we check by comparing +\section{Answering branch infix regular questions} + +With the above problem solved, we are ready to finish our algorithm for branch +infix regular questions. Recall that we have replaced the input tree $T$'s +vertices with copies of $Q$, then connected and colored them in an analogous way +as in the word case from Section \ref{wordinfix}. We additionally remember in +each vertex $v$ a unique identifier of the connected component of vertices of +the same color that it is in (the identifiers can be the root vertices of each +such component), call this data $\componenttable[v]$. + +For each color $c$, we will preprocess the above graph for answering questions +of the form ``if we start in a vertex $v$ colored with $c$, which is the first +copy of $Q$ on the path towards the copy of $Q$ that contains $y$?''. To achieve +this, we create a copy of $T$ in which we mark the vertices where an edge from a +$c$-colored vertex points to a vertex with a lower color. This tree we +preprocess for highest marked descendant on path questions, solved in the +previous section. + +Now question answering can proceed similar to the word case. Given a question +``does the word on vertices from $x$ down to $y$ belong to $L$?'' look at the +vertex $x.q_0$ and consider its color $c$. In the copy of $Q$ corresponding to +$y$ consider the vertex $y.q$, the unique vertex here of color $c$. If it is in +the same connected component as $x.q_0$ (which we check by comparing $\componenttable[x.q_0]$ with $\componenttable[y.q]$), we can immediately answer whether or not $A$ will accept the word on this path based on whether this state -is accepting. If that is the case then we have not changed connected components, -thus there is a single-color path from $x.q_0$ down to $y.q$ and $q$ is indeed -the state $A$ would have ended in after running on the word given by the labels -from $x$ down to $y$. +is accepting. Indeed, if that is the case then we have not changed connected +components, thus there is a single-color path from $x.q_0$ down to $y.q$ and $q$ +is indeed the state $A$ would have ended in after running on the word given by +the labels from $x$ down to $y$. Otherwise, we need to jump down to a lower copy of $Q$. We can find the first such copy where the color on our path changes from $c$ to something lower by -issuing a highest marked descendant on path query on the marked tree we created -for color $c$. The answer to this query exactly corresponds to the point where -the path of color $c$ from our initial state merges into a lower color $c'$ on -the path towards $y$. From here we continue as at the beginning, checking -$\componenttable$ to see if we can answer immediately, or taking another jump -down. Handling each jump takes constant time, and the number of jumps is bounded -by $|Q|$ since we can only jump to a lower color. Thus we can answer branch -infix regular queries in constant time. +asking a highest marked descendant on path question on the marked tree we +created for color $c$. The answer to this question exactly corresponds to the +point where the path of color $c$ from our initial state merges into a lower +color $c'$ on the path towards $y$. From here we continue as at the beginning, +checking $\componenttable$ to see if we can answer immediately, or taking +another jump down. Handling each jump takes constant time, and the number of +jumps is bounded by $|Q|$ since we can only jump to a lower color. Thus we can +answer branch infix regular questions in constant time. \chapter{MSO Query Answering on Trees}\label{mso-query-answering} @@ -718,15 +724,15 @@ $a_1 \ldots a_k$ (where $k = |\vec{X}|$ and each $a_i \in \{ 0, 1 \}$) should be 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 queries on trees by solving -relabel regular queries 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}$). Preprocess $A$ and $T'$ for -relabel regular queries. Now a relabeling of $T'$'s vertices corresponds to -selecting a specific valuation $\vec{W}$ of $\vec{X}$, thus answering whether or -not $A$ accepts the relabeled tree is equivalent to answering whether or not $T -\models \varphi(\vec{W})$. +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 +$\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}$). +Preprocess $A$ and $T'$ for relabel regular questions. Now a relabeling of +$T'$'s vertices corresponds to selecting a specific valuation $\vec{W}$ of +$\vec{X}$, thus answering whether or not $A$ accepts the relabeled tree is +equivalent to answering whether or not $T \models \varphi(\vec{W})$. This concludes the proof of the lemma, and Theorem \ref{mso-query-answering-theorem} will be proved if we prove: @@ -739,15 +745,15 @@ This concludes the proof of the lemma, and Theorem The rest of this chapter is dedicated to proving Theorem \ref{relabel-regular-queries-theorem}. -\section{Relabel Regular Queries on Trees} +\section{Relabel Regular Questions on Trees} Fix a tree automaton $A$ and take a $\Sigma$-labeled binary tree $T$. -We'll preprocess the tree in such a way that when given a relabel query, we'll -be able to partition the tree into linearly (with respect to the query's size) -many parts, then, in a bottom-up fashion, compute the state in the root of each -part in the relabeled tree. The computation for each part will take constant -time. +We'll preprocess the tree in such a way that when given a relabel question, +we'll be able to partition the tree into linearly (with respect to the +question's size) many parts, then, in a bottom-up fashion, compute the state in +the root of each part in the relabeled tree. The computation for each part will +take constant time. Partitioning into the $O(m)$ parts we're interested in will take time $O(m \log m)$, then after the bottom-up computation we will arrive at the root's state in @@ -863,7 +869,7 @@ minimal partition ready set containing $W$. the size of the closure is linear in the size of $W$. \end{lemma} -Proof: In the preprocessing step, we will preprocess the tree for LCA queries, +Proof: In the preprocessing step, we will preprocess the tree for LCA questions, and assign each vertex $v$ its in-order number, $\infixtable[v]$. Now to compute the closure of $W$, we first sort the vertices in $W$ with @@ -897,9 +903,9 @@ $O(m)$. Consider the following set of vertices: U := \{ v \;|\; v = LCA(v_i, v_{i+1}) \text{ for $1 \leq i \leq m - 1$} \} \end{equation*} -$U$ is of size $O(m)$ and can be computed in time $O(m)$ by issuing LCA queries -to successive pairs of the sorted $W$. We claim that $W' := W \cup U$ is the LCA -closure of $W$. +$U$ is of size $O(m)$ and can be computed in time $O(m)$ by issuing LCA +questions to successive pairs of the sorted $W$. We claim that $W' := W \cup U$ +is the LCA closure of $W$. Let's define $u_i := LCA(v_i, v_{i+1})$. By Observation \ref{lca-observation}, each $u_i$ falls between $v_i$ and $v_{i+1}$ in the infix @@ -938,12 +944,12 @@ are in $W$, thus showing $W'$ is LCA closed and finishing the proof of Lemma \section{Computing root states of parts} -Let's now discuss how we will use LCA paritions to solve the relabel query -problem. Our approach is the following: given a query $v_1 \mapsto a_1, \ldots, -v_m \mapsto a_m$, let $W = \{ v_1, \ldots, v_m \}$. Consider the partition of -$T$ with respect to $W$. We will show how to compute $A$'s state in the root of -each part of the partition, after the tree had been relabeled. Per our -definition of the partition, we have three types of parts to consider: +Let's now discuss how we will use LCA paritions to solve the relabel questions +problem. Our approach is the following: given a question $v_1 \mapsto a_1, +\ldots, v_m \mapsto a_m$, let $W = \{ v_1, \ldots, v_m \}$. Consider the +partition of $T$ with respect to $W$. We will show how to compute $A$'s state in +the root of each part of the partition, after the tree had been relabeled. Per +our definition of the partition, we have three types of parts to consider: \begin{enumerate} \item A subtree rooted at vertex $v$. @@ -964,7 +970,7 @@ label. The third is the interesting case, that of a subtree with a hole. Consider the path from the hole $w$ up to the root $v$. What we claim is that the question ``if $A$'s state in $w$ is $q$, is the state in $v$ going to be $q'$?'' can be -answered with a branch infix regular query. +answered with a branch infix regular question. \subsection{Computing the root state of a subtree with a hole} @@ -1045,26 +1051,27 @@ the current vertex's left or right child. The automaton works as follows: This automaton recognizes exactly $L_{q,q'}$, by performing essentially the same computation we described before. This completes the proof of the lemma. -Our algorithm for branch infix regular queries dealt with top-down queries, but -regular languages are reversible. So we preprocess $T$ for branch infix regular -queries for each language $L_{q, q'}^R$. A question about whether the word on -the path from $x$ down to $y$ belongs to $L_{q, q'}^R$ is the same as asking if -the word from $y$ up to $x$ belongs to $L{q,q'}$. Note that the number of -languages we need to preprocess for is constant in the size of the tree -- it +Our algorithm for branch infix regular questions dealt with top-down questions +(i.e. the word we ask about runs from a higher vertex down to its descendant). +Regular languages are reversible, so we can preprocess $T$ for branch infix +regular questions for each language $L_{q, q'}^R$. A question about whether the +word on the path from $x$ down to $y$ belongs to $L_{q, q'}^R$ is the same as +asking if the word from $y$ up to $x$ belongs to $L{q,q'}$. Note that the number +of languages we need to preprocess for is constant in the size of the tree -- it only depends on the size of the automaton. Given the subtree of $x$ with hole $y$, once we've computed $y$'s new state $q$, to compute $x$'s new state, take $x'$ -- $x$'s child in the direction of $y$, find $q' \in Q$ such that the path from $x'$ to $y$ belongs to $L_{q, q'}^R$ -(using branch infix regular queries; since $A$ is deterministic, there will be -exactly one such $q'$). Now from $q'$, the state of $x$'s other child, and -$x$'s new label, use $A$'s transition function to compute $x$'s new state. +(using branch infix regular questions; since $A$ is deterministic, there will be +exactly one such $q'$). Now from $q'$, the state of $x$'s other child, and $x$'s +new label, use $A$'s transition function to compute $x$'s new state. Since $T$'s root is the root of one of the parts of our LCA partition, in the end we will know whether or not $A$ accepts $T$ after relabeling. Handling each part takes constant time, and there are $O(m)$ parts to handle. We did require -$O(m \log m)$ time to sort the query's vertices when computing their LCA -closure, thus query handling takes time $O(m \log m)$. +$O(m \log m)$ time to sort the vertices mentioned in the question when computing +their LCA closure, thus question answering takes time $O(m \log m)$. \printbibliography -- cgit v1.2.3