wiki_research

commit de1032058975fef2a96bcc692e2bf6b492655e6e
parent c4a1d201611bda5e0c0d27f7903bc09a31ecd59c
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed,  6 May 2026 00:13:53 +0200

Merge remote-tracking branch 'origin/master'

Diffstat:
fundamental_theorem_of_arithmetic
 | 
7
+++++++
incremental_maintenance_tuple_testing
 | 
2
+-
knowledge_compilation
 | 
4
+++-
prime_decomposition
 | 
11
+++++++++++
provenance
 | 
1
+
query
 | 
2
++
turing_machine
 | 
2
+-
weakly_connected_graph
 | 
2
++

8 files changed, 28 insertions(+), 3 deletions(-)
diff --git a/fundamental_theorem_of_arithmetic b/fundamental_theorem_of_arithmetic
@@ -0,0 +1,7 @@
+# Fundamental theorem of arithmetic
+
+https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
+
+Up: [arithmetic]
+
+Aliases: decomposition prime numbers
diff --git a/incremental_maintenance_tuple_testing b/incremental_maintenance_tuple_testing
@@ -1,5 +1,5 @@
 # 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 [marked_ancestor_problem]
+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/knowledge_compilation b/knowledge_compilation
@@ -1,6 +1,6 @@
 # Knowledge compilation
 
-Classes of [circuit] ensuring tractability
+Classes of [circuits] for which some tasks are tractable
 
 - [knowledge_compilation_classes]
 - connections to [arithmetic_circuits]
@@ -11,6 +11,8 @@ Classes of [circuit] ensuring tractability
 
 [circuit_bounds_vs_complexity_bounds]
 
+- [knowledge_compilation_open_problems]
+
 Up: [theoretical_computer_science]
 
 Aliases: KC
diff --git a/prime_decomposition b/prime_decomposition
@@ -0,0 +1,11 @@
+# Prime decomposition
+
+The [graph_decomposition] of a [graph] in a [cartesian_product] of [graphs]
+
+Can be computed in [linear_time], cf [crespelle2013linear]
+
+Not necessarily unique but unique for [weakly_connected_digraphs] (up to graph isomorphism and reordering of factors), cf [crespelle2013linear]
+
+Up: [graph_decomposition]
+
+See also: [decomposition_prime_numbers], [prime_number], [prime_graph]
diff --git a/provenance b/provenance
@@ -32,6 +32,7 @@ Kinds of provenance:
 
 [Computational_problems]:
 - [provenance_computation]
+- [query_relevance]
 
 [Research_questions]:
 - [provenance_size]
diff --git a/query b/query
@@ -8,6 +8,8 @@
 - [query_with_negation]
 - [database_returning_queries]
 - [query_constants] / [constant_free_query]
+- [match]
+  - [minimal_match]
 
 ## Problems
 
diff --git a/turing_machine b/turing_machine
@@ -24,6 +24,6 @@
 
 Up: [theoretical_computer_science]
 
-See also: [ram_model], [church_turing_thesis], [alan_turing], [pushdown_automaton], [turing_complete], [decidability], [recursively_enumerable], [kolmogorov_complexity], [busy_beaver]
+See also: [ram_model], [church_turing_thesis], [alan_turing], [pushdown_automaton], [turing_complete], [decidability], [recursively_enumerable], [kolmogorov_complexity], [busy_beaver], [turing_completeness]
 
 Aliases: Turing machines
diff --git a/weakly_connected_graph b/weakly_connected_graph
@@ -5,3 +5,5 @@ A [directed_graph] which is [weakly_connected], i.e., has only one [weakly_conne
 Up: [directed_graph]
 
 See also: [strongly_connected_graph], [graph_connected]
+
+Aliases: weakly connected digraph, weakly connected digraphs