commit a963b6c4fba9522a4b8e48cb18a7bacb212845bc
parent 23bd3fad52e1270802bff2334141cbbabdb7c5b7
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 20 Feb 2025 17:32:25 +0100
commit with codex
Diffstat:
16 files changed, 117 insertions(+), 13 deletions(-)
diff --git a/ac0 b/ac0
@@ -1,9 +0,0 @@
-# Ac0
-
-[ac] circuit with constant [depth] (and unbounded [fan_in], and polynomial size)
-
-AC0 = [first_order_logic] + arbitrary numerical predicates arbitrary arity
-
-Up: [ac]
-
-See also: [acc0]
diff --git a/circuit b/circuit
@@ -12,6 +12,7 @@
- [boolean_circuit]
- [arithmetic_circuit]
- [probabilistic_circuit]
+- [Semiring_circuit]
- [formula]
## Problems
diff --git a/clique b/clique
@@ -17,3 +17,5 @@ clique on [hypergraph]: [hyperclique]
Up: [graph]
See also: [cliquewidth], [fine_grained_complexity], [treewidth], [graph_minor], [graph_complete], [hyperclique]
+
+Aliases: cliques
diff --git a/conjunctive_query_boolean b/conjunctive_query_boolean
@@ -3,3 +3,5 @@
[conjunctive_query] with no [output_variable], all variables are [existentially_quantified]
Up: [conjunctive_query], [query_boolean]
+
+Aliases: Boolean CQ, Boolean CQs
diff --git a/database_instance b/database_instance
@@ -0,0 +1,11 @@
+# Database instance
+
+A set of [relations] containing [tuples] or [facts], for the [relations] defined in a [relational_signature]
+
+[named_perspective] vs [unnamed_perspective]
+
+Up: [database_theory]
+
+Aliases: database
+
+See also: [instance]
diff --git a/database_repairs b/database_repairs
@@ -0,0 +1,16 @@
+# Database repairs
+
+A modification of a [database] to obtain a [database] which satisfies some [integrity_constraints]
+
+[repair_notions]
+
+[Computational_problems]:
+
+- [consistent_query_answering]
+- [repair_counting]
+
+Up: [database_theory]
+
+See also: [language_repair], [graph_modification], [query_repairs], [data_cleaning]
+
+Aliases: database repair
diff --git a/ehrenfeucht_fraisse_game b/ehrenfeucht_fraisse_game
@@ -0,0 +1,18 @@
+# EF-game
+
+Spoiler plays in [structure] A by marking a [vertex], Duplicator answers in [structure] B
+
+The structures induced by the [pebbles] must be [isomorphic]
+
+- Number of rounds necessary to distinguish both [structures]
+ - connections to types nombre de rounds nécessaires pour distinguer les deux structures ([quantifier_rank])
+- Number of [pebbles] needed
+ - connection to [FOk]
+
+[MSO] EF-game: the players can pebble sets
+
+Up: [logic], [games]
+
+See also: [bisimulation], [homomorphic_equivalence], [prover_verifier_game]
+
+Aliases: EF game, EF games
diff --git a/gate b/gate
@@ -0,0 +1,11 @@
+# Gate
+
+A [vertex] of a [circuit], when seen as a [DAG]
+
+May be labeled by a [variable] for [variable_gates], or labeled by an [operator], e.g., [conjunction] or [disjunction] or [negation] for [Boolean_circuits]
+
+Up: [circuit]
+
+Aliases: gates
+
+See also: [wire]
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]
+See also: [graph_homomorphism], [canonical_labeling], [weisfeiler_leman], [graph_automorphism], [quantum_isomorphism]
Aliases: graph isomorphic
diff --git a/homomorphism_equivalence b/homomorphism_equivalence
@@ -0,0 +1,11 @@
+# Homomorphism equivalence
+
+A and B are homomorphically equivalent if there is a [homomorphism] from A to B and a [homomorphism] from B to A
+
+It is an [equivalence_relation]: [transitivity] is because the [composition] of two [homomorphisms] is a [homomorphism]
+
+Up: [homomorphism], [equivalence]
+
+See also: [minimization_conjunctive_query], [bisimulation]
+
+Aliases: homomorphic equivalence, homomorphically equivalent
diff --git a/integrity_constraint b/integrity_constraint
@@ -10,3 +10,5 @@
See also: [logic]
Up: [databases]
+
+Aliases: integrity constraints
diff --git a/negation b/negation
@@ -9,4 +9,4 @@
Up: [logic]
-Aliases: negated
+Aliases: negated, negations
diff --git a/polynomial b/polynomial
@@ -3,8 +3,21 @@
- [polynomial_equation]
- [lagrange_interpolation]
-Up: [mathematics]
+Types:
+
+- [polynomial_homogeneous]
+- [polynomial_multivariate]
+ - [polynomial_multilinear]
+- [polynomial_irreducible]
+- [polynomial_factored]
+- [polynomial_expanded]
+
+Concepts:
-See also: [polynomial_irreducible], [monomial]
+- [monomial]
+- [polynomial_degree]
+- [root]
+
+Up: [mathematics]
Aliases: polynomials
diff --git a/query_with_negation b/query_with_negation
@@ -0,0 +1,9 @@
+# Query with negation
+
+[query] featuring [negation]
+
+- [conjunctive_query_signed]
+
+Up: [query], [negation]
+
+Aliases: queries negation, query negation, query negations
diff --git a/repair_notions b/repair_notions
@@ -0,0 +1,7 @@
+# Repair notions
+
+- [subset_repair]
+- [optimal_subset_repair], a [subset_repair] that [optimizes] a cost
+- can also do [insertions] of [tuples] in some cases
+
+Up: [database_repairs]
diff --git a/semiring_circuit b/semiring_circuit
@@ -0,0 +1,10 @@
+# Semiring circuit
+
+A [circuit] whose [gates] correspond to [operations] in a specific [semiring]
+
+Special cases:
+
+- [Boolean_circuit]
+- [Arithmetic_circuit]
+
+Up: [circuit]
