commit 9000341fa710c499c6a259d01742420374750e8c
parent 2f73af16ab4a6d1fb82fa898098db66df1aa4bb0
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 18 Feb 2025 11:54:17 +0100
commit with codex
Diffstat:
12 files changed, 70 insertions(+), 5 deletions(-)
diff --git a/automata_weighted b/automata_weighted
@@ -14,6 +14,8 @@ given a [word]:
Schützenberger, 1961
+- [automata_weighted_conjugacy]
+
Up: [automata]
See also: [weighted_mso]
diff --git a/chase b/chase
@@ -1,9 +1,17 @@
# Chase
-Process for [database_dependency] to construct [universal_model]
+Given [database_dependencies] and an [instance], construct a (possibly infinite) [universal_model]
- [chase_termination]
- [gerlach2023general]:
- - cf "weakly acyclic" and other sufficient conditions for chase termination
+ - cf [weakly_acyclic_TGDs] and other sufficient conditions for chase termination
+
+Variants:
+
+- [chase_restricted]
+- [chase_oblivious]
+- [chase_core]
+
+Can be used for [query_optimization]
Up: [database_theory]
diff --git a/chase_termination b/chase_termination
@@ -0,0 +1,10 @@
+# Chase termination
+
+depends on the kind of [chase]:
+- [chase_oblivious]
+- [chase_restricted]
+
+recent work: [hanisch2024chase]
+ - idea: beyond [ptime] [data_complexity]
+
+Up: [chase], [termination]
diff --git a/core b/core
@@ -0,0 +1,21 @@
+# Core
+
+The [core] of an [instance] A is a [subinstance] B of A such that there is no [homomorphism] from B to a strict [subinstance] B' of B
+- this is unique up to [isomorphism]
+- it is equal to A if there is no [endomorphism] from A to a strict [subinstance] of A
+
+[computational_problem] of computing the core:
+- checking if a [graph] is its own core
+ - clearly in [coNP] (guess the [homomorphism])
+ - [conp_complete]
+ - https://cstheory.stackexchange.com/questions/2733/what-is-the-best-exact-algorithm-to-compute-the-core-of-a-graph
+- checking if input [graph] G is core of input [graph] H
+ - is in [dp]:
+ - guess existence of [homomorphism]
+ - guess inexistence of other [homomorphism]
+ - is [dp_complete] by [fagin2005data2]
+ - https://cstheory.stackexchange.com/questions/2733/what-is-the-best-exact-algorithm-to-compute-the-core-of-a-graph
+
+Up: [homomorphism]
+
+See also: [chase_core]
diff --git a/disjoint_union b/disjoint_union
@@ -3,3 +3,5 @@
The [union] of two [sets] that are [disjoint]
Up: [union]
+
+Aliases: disjoint unions
diff --git a/equation b/equation
@@ -9,4 +9,4 @@
Up: [mathematics]
-See also: [disequation], [inequation], [equality]
+See also: [disequation], [inequation], [equality], [left_hand_side], [right_hand_side]
diff --git a/graph_bipartite b/graph_bipartite
@@ -1,8 +1,9 @@
# Graph bipartite
-Membership can be tested in [linear_time] with [greedy_algorithm]
+Testing if a [graph] is bipartite can be done in [linear_time] with [greedy_algorithm]
- [deficiency]
+- [complete_bipartite_graph]
Up: [graph_family]
diff --git a/locality_logic b/locality_logic
@@ -0,0 +1,8 @@
+# Locality logic
+
+Works for [FO]
+
+- [Hanf's_theorem], cf [Hanf_normal_form]
+- [Gaifman_normal_form]
+
+Up: [logic]
diff --git a/monoid_positive b/monoid_positive
@@ -0,0 +1,9 @@
+# Monoid positive
+
+A [monoid] being *positive* means x + y = 0 implies x = 0 and y = 0
+
+aka "zero-sum-free"
+
+See also: [semiring_positive]
+
+Up: [monoid]
diff --git a/naturally_ordered_semiring b/naturally_ordered_semiring
@@ -3,3 +3,5 @@
[semiring] with [natural_order]
Up: [natural_order], [semiring]
+
+Aliases: naturally ordered semirings
diff --git a/polynomial b/polynomial
@@ -5,6 +5,6 @@
Up: [mathematics]
-See also: [polynomial_irreducible]
+See also: [polynomial_irreducible], [monomial]
Aliases: polynomials
diff --git a/semiring_absorptive b/semiring_absorptive
@@ -9,3 +9,5 @@ Implies [semiring_idempotence]
Up: [dioid]
See also: [absorptivity]
+
+Aliases: absorptive semiring, absorptive semirings
