commit 26dd5e121126a48366cc12349da7c61121e5f576
parent cf810a03816743e5f6eb03cf4509e533ea671098
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 30 Jan 2025 17:35:29 +0100
commit with codex
Diffstat:
11 files changed, 38 insertions(+), 8 deletions(-)
diff --git a/aggregation b/aggregation
@@ -1,5 +1,7 @@
# Aggregation
+- [queries_aggregate]
+
See also: [quantile], [median], [mean], [sum]
Up: [database_theory]
diff --git a/c2 b/c2
@@ -7,6 +7,8 @@ Does not enjoy [Craig_interpolation], according to [cate2023craig]
Does not enjoy [finite_model_property]
- but [satisfiability] is [decidable], cf [pratt2010two]
+Turns out to be the expressive power of [Weisfeiler_Leman]
+
subclass: [gc2]
Up: [logic]
diff --git a/canonical_labeling b/canonical_labeling
@@ -7,6 +7,8 @@ https://mathoverflow.net/a/11715
also called "graph canonization"
-See also: [graph_isomorphism]
+See also: [graph_isomorphism], [minimization_automaton]
Up: [graph]
+
+Aliases: graph canonical labeling, graph canonization
diff --git a/dsdnnf b/dsdnnf
@@ -5,3 +5,5 @@
not closed under [complementation], cf [vinallsmeeth2024structured] by [harry]
Up: [knowledge_compilation_classes], [ddnnf], [sdnnf]
+
+Aliases: dSDNNFs
diff --git a/finite_model_property b/finite_model_property
@@ -0,0 +1,11 @@
+# Finite model property
+
+A [logical_fragment] has the *finite model property* if whenever a [sentence] of this fragment has a [model] then it has a [finite_model] (of course the converse [implication] is obvious)
+
+Generalizations:
+
+- [finite_controllability]
+
+Up: [property] of [logical_fragment]
+
+Aliases: FMP
diff --git a/homomorphism b/homomorphism
@@ -13,3 +13,5 @@ Variants:
Up: [mathematics]
See also: [core]
+
+Aliases: homomorphisms
diff --git a/logic b/logic
@@ -49,11 +49,12 @@
- [craig_interpolation]
- [ehrenfeucht_fraisse_game]
- [fo_interpretation]
-- [quantifier_rank]
-- [conjunction]
-- [disjunction]
-- [implication]
+- [boolean_connective]
+ - [conjunction]
+ - [disjunction]
+ - [implication]
- [variable]
+ - [free_variable]
- [negation]
- [zero_one_law]
- [craig_interpolation]
@@ -62,7 +63,9 @@
- [monadic]
- [logic_formula]
- [quantifier]
+ - [quantifier_rank]
- [logical_implication]
+- [sentence]
Up: [mathematics], [theoretical_computer_science]
diff --git a/minimization_automaton b/minimization_automaton
@@ -8,3 +8,5 @@
Up: [minimization]
Aliases: minimization of automata, automata minimization, automaton minimization, minimization automata
+
+See also: [canonical_labeling]
diff --git a/query_boolean b/query_boolean
@@ -4,8 +4,10 @@ A [query] whose [query_answer] is a [Boolean]: either the query holds or it does
For [queries] with [free_variables] that are [first_order], the [computational_complexity] of computing [query_answers] is often [PTIME]-equivalent to the Boolean queries obtained by considering each of the polynomially many possible answers and creating a Boolean query by insantianing these [variables] to [constants]
+In [logic], this is called a [sentence]
+
Up: [query]
Aliases: boolean query
-See also: [free_variable], [query_non_boolean]
+See also: [free_variable], [query_non_boolean], [sentence]
diff --git a/query_language b/query_language
@@ -3,7 +3,7 @@
- [conjunctive_query]
- [sjfcq]
- [union_of_conjunctive_queries]
-- [first_order_logic]
+- [first_order_logic]: [first_order_query]
- [monadic_second_order_logic]
## Other formalisms
diff --git a/sdnnf b/sdnnf
@@ -1,5 +1,7 @@
# SDNNF
-like [dnnf] but obeys [structuredness]
+like [DNNFs] but [structured]
Up: [knowledge_compilation_classes], [dnnf], [structuredness]
+
+Aliases: SDNNFs
