commit 299dca684f4e354b51e2fa6c7dbb4cd1815282d7
parent 45912a9fcde25b5b14eec3514b9901180163bd0e
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 27 May 2026 14:35:07 +0200
commit with codex
Diffstat:
14 files changed, 51 insertions(+), 8 deletions(-)
diff --git a/boolean_valuation b/boolean_valuation
@@ -10,4 +10,4 @@ Up: [function], [valuation], [boolean]
See also: [boolean_function]
-Aliases: assignment, Boolean assignment, assignments, Boolean assignments
+Aliases: assignment, Boolean assignment, assignments, Boolean assignments, Boolean valuations
diff --git a/circuit_classes b/circuit_classes
@@ -8,6 +8,8 @@ In [circuit_complexity]:
- [acc] ACC, [acc0], etc.
- liens avec [solvable_group]
-Up: [circuit]
+In [knowledge_compilation]: see [knowledge_compilation_classes]
+
+- [reversible_circuits]
-See also: [knowledge_compilation_classes]
+Up: [circuit]
diff --git a/circuit_negation b/circuit_negation
@@ -0,0 +1,11 @@
+# Circuit negation
+
+The [negation] operator applied to a [circuit]
+
+[computational_problem]: [negation_problem]
+
+Up: [negation] of [circuit]
+
+See also: [de_morgan's_law]
+
+Aliases: circuit negated, circuit complement, circuit complementation, circuit negations
diff --git a/complementation b/complementation
@@ -8,3 +8,5 @@
Up: [logic], [boolean_operator]
Aliases: complement, complements
+
+See also: [negation]
diff --git a/decdnnf_negation b/decdnnf_negation
@@ -0,0 +1,6 @@
+# DecDNNF negation
+
+open whether [decDNNFs] can be negated to a [decDNNF]
+- cf [decolnet2022hard] p124
+
+Up: [negation_problem] of [dec_DNNF]
diff --git a/decision_dnnf b/decision_dnnf
@@ -7,6 +7,8 @@ A *decision-DNNF* is a [DNNF] but only with [decision_gates]
See [cali2026complexity]
+[circuit_negation]: see [decDNNF_negation]
+
Up: [dnnf]
-Aliases: decision_DNNFs, decision-DNNF, decision-DNNFs, decDNNF, decDNNFs
+Aliases: decision_DNNFs, decision-DNNF, decision-DNNFs, decDNNF, decDNNFs, dec DNNF, dec DNNFs
diff --git a/decision_sdnnf b/decision_sdnnf
@@ -3,3 +3,5 @@
A [decision_dnnf] which is a [structured_circuit]
Up: [decision_dnnf], [sdnnf]
+
+Aliases: structured decision DNNF, structured dec DNNF, structured decDNNF,structured decision DNNFs, structured dec DNNFs, structured decDNNFs
diff --git a/disjunctive_normal_form_orthogonal b/disjunctive_normal_form_orthogonal
@@ -3,14 +3,14 @@
[disjunctive_normal_form] where for any two [terms] they are not mutually satisfiable
- so it is an [unambiguous] [disjunctive_normal_form]
-[complement]: [hitting_cnf]
+Their [circuit_negations] are [hitting_cnfs]
note that necessarily the clauses (all except at most one) must be big (at least n/2) to satisfy this condition
-[disjunctive_normal_form_orthogonal_negation]
+The [negation_problem] on them: [disjunctive_normal_form_orthogonal_negation]
Generalization: [k_unambiguous_DNF]
Up: [disjunctive_normal_form]
-Aliases: unambiguous DNF, unambiguous DNFs, orthogonal DNF, orthogonal DNFs
+Aliases: unambiguous DNF, unambiguous DNFs, orthogonal DNF, orthogonal DNFs, uDNF, uDNFs
diff --git a/fbdd b/fbdd
@@ -4,6 +4,8 @@ Free [BDD], i.e., the [variables] are not [ordered] but every [path] in the [BDD
Is a subclass of [DNNF]
+Can be [circuit_negated] in [PTIME] by swapping the [sinks]
+
Up: [bdd]
Aliases: FBDDs
diff --git a/hitting_cnf b/hitting_cnf
@@ -7,3 +7,5 @@ A [conjunctive_normal_form] where the [disjunction] of any two [clauses] is [tau
Up: [conjunctive_normal_form]
See also: [hitting_set]
+
+Aliases: hitting CNFs
diff --git a/knowledge_compilation_classes b/knowledge_compilation_classes
@@ -29,4 +29,4 @@ Up: [knowledge_compilation], [circuit], [Boolean_function_representation]
See also: [circuit_classes], [circuit_condition]
-Aliases: knowledge compilation circuit classes, knowledge compilation circuits, knowledge compilation class
+Aliases: knowledge compilation circuit classes, knowledge compilation circuits, knowledge compilation class, kc circuit class, kc circuit classes
diff --git a/negation b/negation
@@ -6,6 +6,7 @@
- [datalog_negation]
- [negation_as_failure]
- [first_order_logic_existential_positive]
+- [circuit_negation]
Up: [logic]
diff --git a/nobdd b/nobdd
@@ -9,3 +9,5 @@
See also: [nrobp]
Up: [nfbdd]
+
+Aliases: nOBDDs
diff --git a/reversible_circuits b/reversible_circuits
@@ -0,0 +1,11 @@
+# Reversible circuits
+
+A [circuit] where the gates are taken from a family of functions that do [permutations] of the [Boolean_valuations]
+
+See, e.g., [saeedi2013synthesis]
+
+Up: [circuit_classes]
+
+Aliases: circuit reversible, reversible circuit
+
+See also: [quantum_computing]
