wiki_research

commit 6f022cdba450d276d56d9883b62c840e3e0ae1f5
parent 26dd5e121126a48366cc12349da7c61121e5f576
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Fri, 31 Jan 2025 11:51:07 +0100

commit with codex

Diffstat:
conjunctive_query_acyclic
 | 
7
++++++-
conjunctive_query_full
 | 
2
+-
conjunctive_query_inequality
 | 
9
+++++++++
enumeration_delay
 | 
2
++
hypergraph
 | 
1
+
mathematics
 | 
34
+---------------------------------
query
 | 
1
+
strong_exponential_time_hypothesis
 | 
2
++
tree_decomposition
 | 
2
++

9 files changed, 25 insertions(+), 35 deletions(-)
diff --git a/conjunctive_query_acyclic b/conjunctive_query_acyclic
@@ -6,12 +6,17 @@ Can be evaluated by [yannakakis_algorithm] following a [join_tree]
 
 the evaluation problem is in the complexity class [logcfl], and the the complexity is in O(database×query + output)
 
-We can test in linear time if a hypergraph is acyclic and if so build the join tree: [gyo] algorithm
+We can test in linear time if a [hypergraph] is acyclic and if so build the join tree: [gyo] algorithm
+- not so obvious to understand where the [linear_time] claim comes from...
 
 For Boolean queries, even with [self_join], if the query is not acyclic then we can reduce from a hard problem ([triangle_detection] ou [hyperclique_detection])
 
 Special case: [conjunctive_query_hierarchical]
 
+Testing if a CQ is acyclic ([elimination_order]):
+
+- while there is a vertex v whose [closed_neighborhood] (includes v itself) is included in some edge, then delete the vertex
+
 See also: [fagin1983degrees], [guarded_fragment], [alpha_acyclic], [conjunctive_query_cyclic]
 
 Up: [conjunctive_query]
diff --git a/conjunctive_query_full b/conjunctive_query_full
@@ -4,4 +4,4 @@ A [CQ] without [projection]; also called a [join] query
 
 Up: [conjunctive_query], [query_full]
 
-Aliases: full conjunctive query, full CQ, full CQs
+Aliases: full conjunctive query, full CQ, full CQs, join query, join queries
diff --git a/conjunctive_query_inequality b/conjunctive_query_inequality
@@ -0,0 +1,9 @@
+# Conjunctive query inequality
+
+A [CQ] with [inequality_mathematics]
+
+- [union_of_conjunctive_query_inequality]
+
+Up: [conjunctive_query], [inequality_mathematics]
+
+See also: [query_with_negation]
diff --git a/enumeration_delay b/enumeration_delay
@@ -9,3 +9,5 @@ Possible types:
 - [polylog_delay]
 
 Up: [enumeration_definition]
+
+See also: [access_time]
diff --git a/hypergraph b/hypergraph
@@ -7,6 +7,7 @@ generalizes [graph]
 - [vertex]
 - [hyperedge]
 - [primal_graph] aka "Gaifman graph"
+- [subhypergraph]
 
 ## Classes
 
diff --git a/mathematics b/mathematics
@@ -2,39 +2,7 @@
 
 ## Basic concepts
 
-- [set]
-  - [semilinear_set]
-- [partition]
-  - [equivalence_relation]
-- [order]
-  - [partial_order]
-  - [inequality_mathematics]
-- [algebraic_structure]
-  - [monoid]
-  - [semigroup]
-  - [group]
-  - [semiring]
-  - [ring]
-  - [field]
-  - [homomorphism]
-- [distance]
-- [vector]
-- [number]
-- [formal_series]
-- [polynomial]
-- [lattice]
-- [logarithm]
-- [matrix]
-- [function]
-- [equation]
-  - [equation_system]
-  - [inequation]
-  - [disequation]
-- [sequence]
-- [cartesian_product]
-- [plane_mathematics]
-- [modulo]
-- [relation_mathematics]
+[mathematics_basic_concepts]
 
 ## Notions
 
diff --git a/query b/query
@@ -5,6 +5,7 @@
 - [query_full]
 - [query_boolean]
   - [query_non_boolean]
+- [query_with_negation]
 
 ## Problems
 
diff --git a/strong_exponential_time_hypothesis b/strong_exponential_time_hypothesis
@@ -2,6 +2,8 @@
 
 In the vocabulary of [exponential_time_hypothesis] it claims that lim_k s_k = 1
 
+[SETH_fine_grained]
+
 Up: [exponential_time_hypothesis]
 
 Aliases: SETH
diff --git a/tree_decomposition b/tree_decomposition
@@ -7,3 +7,5 @@
 See also: [treewidth]
 
 Up: [tree]
+
+Aliases: tree decompositions