commit af78d60764ddc2ff7d8b7d602eb0ea1a00deee61
parent 13d75b51ea67e0e2e53e0178332573c2226f6a87
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 17 May 2026 12:40:02 +0200
commit with codex
Diffstat:
11 files changed, 40 insertions(+), 9 deletions(-)
diff --git a/abokhamis2024fast b/abokhamis2024fast
@@ -7,3 +7,5 @@
- connections with [information_theory]
Up: [academic_paper] on [conjunctive_query_matrix_multiplication]
+
+Aliases: abokhamis2025fast
diff --git a/datalog_query_evaluation b/datalog_query_evaluation
@@ -19,6 +19,8 @@ An important idea is to run the [CQs] of the [rule_bodies] efficiently: [conjunc
[zhang2023enhancing]: [query_evaluation] of [datalog] via [hypertreewidth]
+- [datalog_fine_grained]
+
Up: [datalog], [query_evaluation]
See also: [query_optimization]
diff --git a/graph_theorem b/graph_theorem
@@ -4,7 +4,11 @@
- [four_color_theorem]
- [strong_perfect_graph_theorem]
- [123_conjecture]
+- [friendship_theorem]
+- [handshaking_lemma]
-Up: [graph]
+Up: [graph], [theorems]
Aliases: graph theorems
+
+See also: [graph_theory]
diff --git a/graph_theory b/graph_theory
@@ -1,9 +1,15 @@
# Graph theory
-- [friendship_theorem]
-- [handshaking_lemma]
-- [extremal_graph_theory]
+## Subfields
+
- [games_on_graphs]
- [pursuit_evasion]
+- [extremal_graph_theory]
+- [structural_graph_theory]
+- [graph_algorithms]
+
+## Graph theorems
+
+[graph_theorems]
Up: [theoretical_computer_science] on [graph]
diff --git a/multiple_context_free_grammar b/multiple_context_free_grammar
@@ -5,3 +5,5 @@
Up: [context_free_grammar]
Aliases: MCFG, MCFGs
+
+See also: [multiple_context_free_language]
diff --git a/nfa_acceptance b/nfa_acceptance
@@ -1,10 +1,12 @@
# NFA acceptance
-The [automaton_acceptance] problem for an [NFA]
+The [automaton_acceptance] problem for an [NFA], of course in [combined_complexity]
Can be solved by [state_set_simulation]
-[Hardness_hypothesis] that this is optimal in [backurs2016which], see also [bringmann2024nfa]
+[Hardness_hypothesis] that this is optimal in [backurs2016which]
+
+[NFA_acceptance_classification]
Up: [automaton_acceptance], [NFA]
diff --git a/reachability b/reachability
@@ -8,4 +8,4 @@
Up: [computational_problem], [graph_theory]
-Aliases: reachability problem, reachability problems
+Aliases: reachability problem, reachability problems, graph reachability
diff --git a/rpq_query_evaluation b/rpq_query_evaluation
@@ -13,6 +13,8 @@ survey: [barcelo2013querying]
- [rpq_counting_answers]
- [rpq_output_sensitive]
+Generalization: [CFL_reachability]
+
Up: [regular_path_query], [query_evaluation]
Aliases: RPQ evaluation
diff --git a/subword_closure b/subword_closure
@@ -6,4 +6,4 @@ By definition it is a [subword_closed_language]
Up: [subword]
-See also: [subsequence_closure]
+See also: [subsequence_closure], [automata_subword_closed]
diff --git a/tree_decomposition_updating b/tree_decomposition_updating
@@ -4,3 +4,5 @@
- [gottlob2022incremental], sur [generalized_hypertree_decomposition]
Up: [incremental_maintenance] of [tree_decomposition]
+
+Aliases: tree decomposition incremental maintenance
diff --git a/zhao2024evaluating b/zhao2024evaluating
@@ -6,4 +6,13 @@
- has [lower_bounds] but still over a class of programs, not over a specific program
- reduction from [clique]
-Up: [academic_paper] on [datalog_semiring_query_evaluation]
+mentions cases:
+
+- [chain_datalog], cf [yannakakis1990graph]
+ - connected to [CFGs] / [context_free_reachability]
+ - [cubic] [data_complexity]
+ - chain rules of the form R(x,y) <- P1(x,z1) ... Pn(zn-1,y)
+
+Up: [academic_paper] on [datalog_semiring_query_evaluation], [datalog_fine_grained]
+
+See also: [zhao2024evaluatingb]
