wiki_research

commit 23bd3fad52e1270802bff2334141cbbabdb7c5b7
parent ab186f70a0c9fc4ec635667dc2c269ebdbc50297
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Thu, 20 Feb 2025 12:06:21 +0100

commit with codex

Diffstat:
bag_cq_containment
 | 
9
+++++++++
bellman_ford_algorithm
 | 
2
++
conjunctive_query
 | 
1
+
conjunctive_query_inequality
 | 
2
++
exponentiation
 | 
2
+-
integers
 | 
2
++
logic
 | 
1
+
parikhs_theorem
 | 
4
+++-
semiring_absorptive
 | 
2
++
single_source_shortest_path
 | 
3
++-
sjfcq
 | 
4
+++-

11 files changed, 28 insertions(+), 4 deletions(-)
diff --git a/bag_cq_containment b/bag_cq_containment
@@ -0,0 +1,9 @@
+# Bag cq containment
+
+bag [query_containment] for [CQs] is [open_problem]
+
+- introduced in [chaudhuri1993optimization]
+- withdrawn claim of [Pi_2_p]-hardness
+- only known [lower_bound] is [NP_hard]
+
+Up: [containment_bag_semantics], [CQs]
diff --git a/bellman_ford_algorithm b/bellman_ford_algorithm
@@ -6,3 +6,5 @@
 Up: [shortest_path_algorithm]
 
 Aliases: Bellman-Ford, Bellman Ford
+
+See also: [single_source_shortest_path_faster]
diff --git a/conjunctive_query b/conjunctive_query
@@ -12,6 +12,7 @@ Subclasses:
 
 Generalization:
 - [conjunctive_query_signed]
+- [conjunctive_query_inequalities]
 
 Up: [query_language]
 
diff --git a/conjunctive_query_inequality b/conjunctive_query_inequality
@@ -7,3 +7,5 @@ A [CQ] with [inequality_mathematics]
 Up: [conjunctive_query], [inequality_mathematics]
 
 See also: [query_with_negation]
+
+Aliases: CQ inequalities
diff --git a/exponentiation b/exponentiation
@@ -1,7 +1,7 @@
 # Exponentiation
 
 - [graph_exponentiation]
-- [exponentiation_by_squaring]
+- [exponentiation_by_squaring] or [fast_exponentiation]
 
 Up: [mathematics_operation]
 
diff --git a/integers b/integers
@@ -5,3 +5,5 @@ The set \mathbb{Z} of [natural_numbers] or the [negative_numbers] (including [ze
 Up: [number]
 
 Aliases: integer, ZZ
+
+See also: [rational_numbers]
diff --git a/logic b/logic
@@ -19,6 +19,7 @@
 - [monadic_second_order_logic]
 - [separator_logic]
 - [description_logics]
+- [LTL]
 
 ## Problems
 
diff --git a/parikhs_theorem b/parikhs_theorem
@@ -4,4 +4,6 @@ https://en.m.wikipedia.org/wiki/Parikh's_theorem
 
 [regular_language] and [context_free_language] have same kind of [parikh_image]
 
-Up: [parikh_image]
+The [Parikh_image] of a [CFL] is a [union] of finitely many [linear_sets], where a [linear_set] is an expression of the form u + M alpha over alpha the vectors with integer values, for u an origin vector and M a [matrix]
+
+Up: [theorem] about [parikh_image]
diff --git a/semiring_absorptive b/semiring_absorptive
@@ -6,6 +6,8 @@ Implies [semiring_idempotence]
 
 [absorptive_semiring_notes]
 
+Generalization: [semiring_p_stable]
+
 Up: [dioid]
 
 See also: [absorptivity]
diff --git a/single_source_shortest_path b/single_source_shortest_path
@@ -1,5 +1,6 @@
 # Shortest path single source
 
-[single_source_shortest_path_algorithm]
+- [single_source_shortest_path_algorithm]
+  - [single_source_shortest_path_faster]
 
 Up: [shortest_path]
diff --git a/sjfcq b/sjfcq
@@ -1,7 +1,9 @@
 # SJFCQ
 
-[conjunctive_query] without [self_join]
+[conjunctive_query] without [self_joins]
 
 [dichotomy] for [pqe] in [dalvi2007efficient]
 
 Up: [conjunctive_query], [self_join]
+
+Aliases: self join free CQ, self join free CQs, selfjoin free CQ, selfjoin free CQs, cq self join free, cqs self join free