commit c19dafd9eeb3522bcf73ef63feb5d53e76a78186
parent cf4c4caedece8da081b224d73dd7ed4255061903
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 13 Aug 2026 18:33:01 +0200
commit with codex
Diffstat:
20 files changed, 45 insertions(+), 9 deletions(-)
diff --git a/conjunctive_query_acyclic b/conjunctive_query_acyclic
@@ -21,6 +21,8 @@ Special case:
- [acyclic_SJFCQ]
+Generalization: [acyclic_CRPQ]
+
See also: [fagin1983degrees], [guarded_fragment], [alpha_acyclic], [conjunctive_query_cyclic]
Up: [conjunctive_query], [query_acyclic]
diff --git a/context_free_grammar b/context_free_grammar
@@ -10,6 +10,7 @@
- [context_free_language]
- [proto_word]
- [derivation]
+- [epsilon_production]
## Equivalence
diff --git a/counting_mso b/counting_mso
@@ -5,6 +5,6 @@
- all assignments have a value obtained by summing the value of the variables
- we want to compute some aggregation of the weights of all assignments
-See also: [weighted_mso]
+See also: [weighted_mso], [CMSO]
Up: [monadic_second_order_logic], [counting_weighted_mso]
diff --git a/crpq_acyclic b/crpq_acyclic
@@ -0,0 +1,9 @@
+# Acyclic CRPQ
+
+A [CRPQ] which is an [acyclic_query]
+
+Efficient [output_sensitive_algorithm] in [data_complexity] [abokhamis2026acyclic], not worse than for the underlying [acyclic_CQ]
+
+Up: [crpq], [acyclic_query]
+
+Aliases: Acyclic CRPQ, Acyclic CRPQs
diff --git a/dynamic_programming b/dynamic_programming
@@ -6,6 +6,8 @@
- [dynamic_dynamic_programming]
+- [nonserial_dynamic_programming]
+
Up: [algorithm_type]
See also: [memoization]
diff --git a/epsilon_transition b/epsilon_transition
@@ -5,3 +5,5 @@ A [transition] labeled with the [empty_word]. It can be traversed by a [run] wit
Up: [transition]
Aliases: epsilon transitions
+
+See also: [epsilon_transition_removal]
diff --git a/gray_code b/gray_code
@@ -13,6 +13,10 @@ construction:
- [pseudo_gray_code]
+[gray_code_compression]
+
Up: [enumeration]
See also: [middle_levels_conjecture], [torsten]
+
+Aliases: gray codes
diff --git a/incremental_maintenance_tuple_testing b/incremental_maintenance_tuple_testing
@@ -1,5 +0,0 @@
-# Incremental maintenance tuple testing
-
-For sufficiently complicated problems, it is not possible in general to have [tuple_testing] in O(1) and [update] support in less than O(log n), via result on [existential_marked_ancestor_problem]
-
-Up: [incremental_maintenance], [tuple_testing]
diff --git a/mathematics b/mathematics
@@ -34,6 +34,7 @@
- [kissing_number_problem]
- [moving_sofa_problem]
- [tiling], cf https://en.m.wikipedia.org/wiki/Heesch%27s_problem
+- [tarski's_high_school_algebra_problem]
## [theorem]
diff --git a/monadic_second_order_logic b/monadic_second_order_logic
@@ -12,6 +12,7 @@ Extensions:
- [counting_monadic_second_order_logic]
- [weighted_MSO]
- [guarded_second_order_logic]
+- [CMSO]
[Computational_complexity]:
diff --git a/permanent b/permanent
@@ -0,0 +1,9 @@
+# Permanent
+
+https://en.wikipedia.org/wiki/Permanent_(mathematics)
+
+[approximation]: cf [jerrum2004polynomial]
+
+Up: [matrix]
+
+See also: [determinant], [immanant]
diff --git a/range_query b/range_query
@@ -7,6 +7,7 @@ Maintain a collection of points and answer queries asking about all the points i
- [range_reporting]: report the points
- [gupta1995further]: range color counting/reporting in [rectangle]
- [range_query_dynamic]
+- [range_distinctness_query]
See also: [skyline], [2d_range_reporting], [range_reporting], [range_tree]
diff --git a/rmq b/rmq
@@ -9,3 +9,5 @@ Can be used for [LCA] and for [longest_common_prefix]
Up: [range_query]
Aliases: range min query, range max query, range minimum query, range maximum query, range min, range max
+
+See also: [range_distinctness_query]
diff --git a/self_reducibility b/self_reducibility
@@ -6,3 +6,5 @@ The paper [jerrum1986random] that defines it shows equivalence of [counting_appr
- it also shows that [counting_approximate] to within a constant factor allows you, for self-reducible problems, to do [counting_approximate] with a [fpras], by going via [sampling_approximate]
Up: [theoretical_computer_science]
+
+Aliases: self reducible, self-reducible, self-reducibility
diff --git a/set_cover_red_blue b/set_cover_red_blue
@@ -10,4 +10,4 @@ The question is how well can it be [approximated], compared to [set_cover_approx
Up: [set_cover_problem]
-See also: [exact_matching]
+See also: [exact_matching], [red_blue_transportation_problem]
diff --git a/sharp_dnnf_approximation b/sharp_dnnf_approximation
@@ -2,6 +2,7 @@
The #DNNF problem admits an [FPRAS] according to [meel2024fpras]
- generalization (uses their result) in [hecher2025alternation]
+ - class [SpanALP]
Up: [sharp_dnnf], [fpras]
diff --git a/shuffle_product_problem b/shuffle_product_problem
@@ -7,3 +7,5 @@ can be done with [dynamic_programming], which gives a [polynomial_time] [algorit
[complete] for [XNLP], cf [bodlaender2026parameterized]
Up: [computational_problem], [shuffle]
+
+See also: [shuffle_product]
diff --git a/spanl b/spanl
@@ -6,6 +6,6 @@ Complete problem: [sharp_nfa]
Defined in [alvarez1993very]
-See also: [spanp]
+See also: [spanp], [spanalp]
Up: [complexity_class], [counting]
diff --git a/st_reliability b/st_reliability
@@ -5,6 +5,8 @@ The case of [network_reliability] with a fixed source and target
Can be posed:
- on [directed_graphs]: [st_reliability_directed]
- on [undirected_graphs]: [st_reliability_undirected]
+ - reduces to [st_reliability_directed]
+ - see [feng2026approximating] Figure 1
- [st_reliability_approximation]
- [st_reliability_provenance]
diff --git a/suffix_array b/suffix_array
@@ -6,4 +6,4 @@ can be used for [longest_common_extension], when adding an [lcp_table]
Up: [stringology], [data_structure]
-See also: [suffix_tree]
+See also: [suffix_tree], [suffixient_set]
