wiki_research

commit 387929beed85c1c0c82e31895b0955d51e7b343d
parent 933a88a52a80b9c5d865057505da7a141a7de722
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Sun, 22 Mar 2026 23:28:39 +0100

commit with codex

Diffstat:
automata_min_plus
 | 
13
+++++++++++++
automata_weighted
 | 
2
++
exact_matching
 | 
4
+++-
integrity_constraint
 | 
2
+-
pseudorandomness
 | 
1
+
query_evaluation
 | 
2
++
query_evaluation_constraint_satisfaction
 | 
5
+++++
query_evaluation_tgds
 | 
7
+++++++
red_blue_yellow_matching
 | 
5
+++++
traveling_salesperson_problem
 | 
11
+++++++++++
tropical_semiring
 | 
2
+-

11 files changed, 51 insertions(+), 3 deletions(-)
diff --git a/automata_min_plus b/automata_min_plus
@@ -0,0 +1,13 @@
+# Min-plus automata
+
+[Weighted_automata] in the [tropical_semiring]
+
+The [deterministic_automata] in this model are less powerful than the [nondeterministic_automata]
+
+It is [decidable] whether an input min-plus automata is equivalent to a [deterministic_automaton] in this setting, cf [almagor2025determinization] and [almagor2026complexity]
+
+Up: [automata_weighted]
+
+See also: [min_plus_matrix_multiplication], [Tropical_semiring]
+
+Aliases: minplus automata, min plus automata, minplus automaton, min plus automaton
diff --git a/automata_weighted b/automata_weighted
@@ -18,6 +18,8 @@ Schützenberger, 1961
 
 - [automata_weighted_conjugacy]
 
+- [automata_min_plus]
+
 Up: [automata]
 
 See also: [weighted_mso]
diff --git a/exact_matching b/exact_matching
@@ -5,6 +5,8 @@
 
 [maalouly2022exact]: this is in [RP] and not known to be in [ptime]
 
-Variant: [exact_matching_parity]
+Variants:
+- [exact_matching_parity]
+- [red_blue_yellow_matching]
 
 Up: [matching]
diff --git a/integrity_constraint b/integrity_constraint
@@ -22,4 +22,4 @@ See also: [logic]
 
 Up: [databases]
 
-Aliases: integrity constraints
+Aliases: integrity constraints, database constraint, database constraints
diff --git a/pseudorandomness b/pseudorandomness
@@ -1,5 +1,6 @@
 # Pseudorandomness
 
 - [prng]
+- [hardness_vs_randomness]
 
 Up: [randomness]
diff --git a/query_evaluation b/query_evaluation
@@ -18,6 +18,8 @@
 
 - [approximate_query_evaluation]
 - [query_approximation]
+- [query_evaluation_constraints]
+- [query_evaluation_constraint_satisfaction]
 
 Up: [database_theory_problem]
 
diff --git a/query_evaluation_constraint_satisfaction b/query_evaluation_constraint_satisfaction
@@ -0,0 +1,5 @@
+# Query evaluation constraint satisfaction
+
+cf [deeds2026query]
+
+Up: [query_evaluation], [constraint_satisfaction_problem]
diff --git a/query_evaluation_tgds b/query_evaluation_tgds
@@ -0,0 +1,7 @@
+# Query evaluation under TGDs
+
+cf [carmeli2026lets]
+
+Up: [query_evaluation_constraints], [TGDs]
+
+Aliases: Query evaluation under TGDs
diff --git a/red_blue_yellow_matching b/red_blue_yellow_matching
@@ -0,0 +1,5 @@
+# Red blue yellow matching
+
+Variant of [exact_matching] with 3 colors, studied in [aprile2026red]
+
+Up: [exact_matching]
diff --git a/traveling_salesperson_problem b/traveling_salesperson_problem
@@ -0,0 +1,11 @@
+# Traveling salesperson problem
+
+https://en.wikipedia.org/wiki/Travelling_salesman_problem
+
+[approximation] when the [distances] correspond to a [metric_space]:
+- [Christofides_algorithm] https://en.wikipedia.org/wiki/Christofides_algorithm
+- slight approximation in [karlin2023slightly]
+
+See also: [chinese_postman_problem]
+
+Up: [computational_problem] on [graphs]
diff --git a/tropical_semiring b/tropical_semiring
@@ -10,6 +10,6 @@ It is an [absorptive_semiring]
 
 Up: [semiring_list]
 
-See also: [mpp_minimum], [tropical], [max_plus_semiring]
+See also: [mpp_minimum], [tropical], [max_plus_semiring], [Min_plus_matrix_multiplication], [automata_min_plus]
 
 Aliases: semiring tropical, min plus semiring, semiring min plus