From b59f97f4f68512d631538f84c7a526a2cb39124e Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
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

