commit 44ef4508b68a0b075fe6c47a6bd7766436947b4d
parent 603895d685b753c0d63066c90c01cdb28a7cb0c0
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 25 May 2026 13:57:58 +0200
commit with codex
Diffstat:
15 files changed, 69 insertions(+), 5 deletions(-)
diff --git a/conjunctive_query b/conjunctive_query
@@ -18,4 +18,4 @@ Up: [query_language]
See also: [conjunction]
-Aliases: CQ, CQs
+Aliases: CQ, CQs, conjunctive queries
diff --git a/density_function b/density_function
@@ -16,6 +16,6 @@ computing its regime on [context_free_languages]: [gawrychowski2010finding]
Up: [automata]
-See also: [universality_automata], [sharp_automaton], [slice], [degree_of_ambiguity], [growth_rate_analysis]
+See also: [universality_automata], [sharp_automaton], [slice], [degree_of_ambiguity], [growth_rate_analysis], [density]
Aliases: density functions
diff --git a/enumeration_cqs b/enumeration_cqs
@@ -13,3 +13,5 @@ With [self_joins]: [enumeration_self_joins]
Up: [enumeration_query_answers] for [conjunctive_query]
See also: [direct_access]
+
+Aliases: CQ enumeration
diff --git a/enumeration_ucqs b/enumeration_ucqs
@@ -19,3 +19,5 @@ open question: [enumeration_ucqs_classifying]
Up: [enumeration] for [union_of_conjunctive_query]
See also: [enumeration_cqs]
+
+Aliases: UCQ enumeration
diff --git a/erdos_distinct_distances_problem b/erdos_distinct_distances_problem
@@ -0,0 +1,11 @@
+# Erdos distinct distances problem
+
+https://en.wikipedia.org/wiki/Erd%C5%91s_distinct_distances_problem
+
+A question about the minimal number of distinct edge distances can be achieved by a planar embedding of a graph (the maximal number is easy to achieve)
+
+Known to be Omega(n / log n) and O(n / sqrt(log n))
+
+See also: [unit_distance_conjecture]
+
+Up: [extremal_combinatorics]
diff --git a/graph_family b/graph_family
@@ -45,6 +45,8 @@ A (generally [infinite]) set of [graphs]
- [leaf_power]
+- [unit_distance_graph]
+
May have the property of being [graph_class_hereditary]
Up: [graph]
diff --git a/hadwiger_conjecture b/hadwiger_conjecture
@@ -0,0 +1,9 @@
+# Hadwiger conjecture
+
+https://en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory)
+
+Asks whether every [graph] with [chromatic_number] k have a k-[clique] as a [graph_minor]
+
+Up: [graph_coloring]
+
+See also: [Hadwiger_nelson_problem]
diff --git a/knowledge_compilation b/knowledge_compilation
@@ -16,3 +16,5 @@ Classes of [circuits] for which some tasks are tractable
Up: [theoretical_computer_science]
Aliases: KC
+
+See also: [provenance_circuit]
diff --git a/knowledge_compilation_classes b/knowledge_compilation_classes
@@ -24,4 +24,4 @@ Up: [knowledge_compilation], [circuit], [Boolean_function_representation]
See also: [circuit_classes], [circuit_condition]
-Aliases: knowledge compilation circuit classes, knowledge compilation circuits
+Aliases: knowledge compilation circuit classes, knowledge compilation circuits, knowledge compilation class
diff --git a/provenance_circuit b/provenance_circuit
@@ -4,6 +4,10 @@ Can use [circuit] for [provenance], e.g.,
- [datalog] provenance: [provenance_circuit_datalog]
- [provenance_mso]: [monadic_second_order_logic] provenance [amarilli2015provenance]
+- [provenance_fo]
+- [provenance_cq]
+ - [provenance_ucq]
+- [provenance_rpq]
Up: [provenance], [circuit]
diff --git a/query_compilation b/query_compilation
@@ -0,0 +1,7 @@
+# Query compilation
+
+computing a representation from a [knowledge_compilation_class] on the [provenance] of a query
+
+see [provenance_circuit]
+
+Up: [knowledge_compilation]
diff --git a/query_evaluation b/query_evaluation
@@ -25,4 +25,4 @@
Up: [database_theory_problem]
-See also: [query_language], [enumeration_query_answers], [homomorphism_problem]
+See also: [query_language], [enumeration_query_answers], [homomorphism_problem], [provenance_circuit]
diff --git a/query_relevance b/query_relevance
@@ -0,0 +1,7 @@
+# Query relevance
+
+Given a [database] D, a [Boolean_query] Q, and a [fact] f of D, we say that f is *relevant* to Q on D if f belongs to a [minimal_match] of Q in D
+
+See [bienvenu2026how]
+
+Up: [provenance]
diff --git a/sequence b/sequence
@@ -4,12 +4,17 @@
- [Kleene_sequence]
- [De_Bruijn_sequence]
-- [arithmetic_progression]
- [hailstone_sequence]
- [Recamans_sequence]
+- [linear_recurrence_sequence]
+ - [arithmetic_progression]
## Concepts
- [subsequence]
+## Open problems
+
+- [skolem_problem]
+
Up: [mathematics]
diff --git a/skolem_problem b/skolem_problem
@@ -0,0 +1,13 @@
+# Skolem problem
+
+https://en.wikipedia.org/wiki/Skolem_problem
+
+The [computational_problem] of [deciding] whether a [linear_recurrence_sequence] takes the value 0
+
+[NP_hard], see [blondel2002deciding]
+
+Up: [sequence]
+
+See also: [skolem_mahler_lech_theorem]
+
+Aliases: Skolem's problem, Pisot problem, Pisot's problem
