wiki_research

commit 1f8e4761803a732802ac4d9c4921a0739e2781a8
parent 0dc7d6bd6d2fefbf19e41912321003c879b8dbee
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed, 14 May 2025 14:43:41 +0200

commit with codex

Diffstat:
bag_cq_containment
 | 
2
++
circuit_algebraic
 | 
7
+++++++
decision_dnnf
 | 
2
++
enumeration_circuit
 | 
2
+-
equivalence_bag_semantics
 | 
7
+++++++
graph_isomorphism
 | 
2
+-
query_equivalence
 | 
3
+++

7 files changed, 23 insertions(+), 2 deletions(-)
diff --git a/bag_cq_containment b/bag_cq_containment
@@ -8,4 +8,6 @@
 
 Recent discussion: [marcinkowski2025bag]
 
+Recent work [konstantinidis2025bag] on [join_on_free_queries]
+
 Up: [containment_bag_semantics], [CQs]
diff --git a/circuit_algebraic b/circuit_algebraic
@@ -0,0 +1,7 @@
+# Circuit algebraic
+
+[wang2024compositional]
+
+Up: [probabilistic_circuit], [algebra]
+
+Aliases: algebraic circuit, algebraic circuits
diff --git a/decision_dnnf b/decision_dnnf
@@ -6,3 +6,5 @@
 - special case: [decision_sdnnf]
 
 Up: [dnnf]
+
+Aliases: decision_DNNFs, decision-DNNF, decision-DNNFs
diff --git a/enumeration_circuit b/enumeration_circuit
@@ -8,7 +8,7 @@ Harder than [satisfiability_boolean] so [np_hard] on general [boolean_circuit]
 
 [enumeration_sdnnf]
 
-[decolnet2023complexity]: [enumeration] of [prime_implicant] on [decision_DNNF]
+[decolnet2023complexity]: [enumeration] of [prime_implicants] on [decision_DNNFs]
 
 Up: [enumeration] on [boolean_circuit]
 
diff --git a/equivalence_bag_semantics b/equivalence_bag_semantics
@@ -0,0 +1,7 @@
+# Equivalence bag semantics
+
+Bag [query_equivalence] is [GI_complete] for [CQs] and [UCQs]
+
+Up: [query_equivalence], [containment_bag_semantics]
+
+See also: [query_equivalence_problem]
diff --git a/graph_isomorphism b/graph_isomorphism
@@ -4,6 +4,6 @@
 
 Up: [isomorphism] of [graph]
 
-See also: [graph_homomorphism], [canonical_labeling], [weisfeiler_leman], [graph_automorphism], [quantum_isomorphism]
+See also: [graph_homomorphism], [canonical_labeling], [weisfeiler_leman], [graph_automorphism], [quantum_isomorphism], [GI_complete]
 
 Aliases: graph isomorphic
diff --git a/query_equivalence b/query_equivalence
@@ -6,6 +6,9 @@ For non-Boolean [queries], on every [database] the [set] of returned [answers] s
 
 [Computational_problem]: [query_equivalence_problem]
 
+- variant: [equivalence_bag_semantics] in [bag_semantics]
+  - or in different [semirings]
+
 Up: [equivalence], [query]
 
 Aliases: query_equivalent