m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2022-12-18 17:14:11 +0100
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2022-12-18 17:14:11 +0100
commit1c2aa53edc01aae92c47e585fd8ae0649f213bea (patch)
tree8b7776dda48a94cd0b6bd01751e5fcc7ffc907bb
parent7fcd1ea90799c22a48b183236c84cb830fd746d2 (diff)
Be more brief
-rw-r--r--presentation/presentation.md16
1 files changed, 7 insertions, 9 deletions
diff --git a/presentation/presentation.md b/presentation/presentation.md
index e2898d4..d3ab7be 100644
--- a/presentation/presentation.md
+++ b/presentation/presentation.md
@@ -69,8 +69,7 @@ singletons.
* I show an $\langle O_{\varphi}(n), O_{\varphi}(m \log{m}) \rangle$ solution to
MSO query answering.
-* Answering is $O_{\varphi}(1)$ when restricting to only first-order free
- variables, matching Kazana's result.
+* $O_{\varphi}(1)$ for first-order free variables, matching Kazana's result.
* Should be understandable by a CS student who has taken undergraduate
algorithmics and automata theory courses.
@@ -117,16 +116,15 @@ Note: computing the partition takes time $O(m \log{m})$ as it uses a sort.
## Computing Roots of Parts - Subtree
-* During preprocessing, we precomputed a run of $A$ over $T$.
-* In a subtree part, no vertices other than the root were relabeled.
-* So we can apply $A$'s transition function to the precomputed states of the
- root's children, and the root's new label.
+* During preprocessing, we precompute $A$'s run over $T$.
+* In a subtree part, only the root was relabeled.
+* Apply $A$'s transition function to the precomputed states of the root's
+ children and the root's new label.
## Computing Roots of Parts - Singleton
* Both of the singleton's children are roots of parts.
-* Since we're working bottom-up, we've already computed the states in the roots
- of those.
+* We're working bottom-up, we've already computed the states in those roots.
* Apply $A$'s transition function to those and the singleton's new label.
## Computing Roots of Parts - Subtree With a Hole
@@ -135,7 +133,7 @@ Note: computing the partition takes time $O(m \log{m})$ as it uses a sort.
* Idea: can be computed by a DFA walking up from hole to root.
* Chapter 3: Branch Infix Regular Questions
* Show how to solve this in $\langle O_A(n), O_A(1) \rangle$.
- * Generalization of a clever algorithm on words.
+ * Generalization of a known algorithm on words.
## Computing Roots of Parts - Subtree With a Hole