From b59f97f4f68512d631538f84c7a526a2cb39124e Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Sat, 11 Dec 2021 14:05:42 +0100 Subject: Explain R notation --- mgr.tex | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'mgr.tex') diff --git a/mgr.tex b/mgr.tex index 0c7054b..ac11a1f 100644 --- a/mgr.tex +++ b/mgr.tex @@ -1055,11 +1055,12 @@ computation we described before. This completes the proof of the lemma. 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. +regular questions for each language $L_{q, q'}^R$ (where $\cdot^R$ denotes the +reversed language). 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$, -- cgit v1.2.3