commit 9a8fcce33a024331e3305000c5320006b9686e68
parent f9937d8dfe330e280724dae627543873e9a218df
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 25 Aug 2025 14:29:20 +0200
commit with codex
Diffstat:
7 files changed, 34 insertions(+), 5 deletions(-)
diff --git a/bdd b/bdd
@@ -9,4 +9,4 @@
Up: [diagram]
-See also: [branching_program], [read_once_branching_program]
+See also: [branching_program], [read_once_branching_program], [decision_tree]
diff --git a/boolean_function_equivalence b/boolean_function_equivalence
@@ -0,0 +1,5 @@
+# Boolean function equivalence
+
+The [computational_problem] of deciding, given two [Boolean_function_representations], whether they represent the same [Boolean_function]
+
+Up: [equivalence_problem]
diff --git a/boolean_function_representation b/boolean_function_representation
@@ -0,0 +1,10 @@
+# Boolean function representation
+
+A [formalism] that represents a [Boolean_function]
+
+- [Boolean_formula]
+- [Boolean_circuit]
+- [decision_tree]
+- [knowledge_compilation_classes]
+
+Up: [formalism] for [Boolean_function]
diff --git a/circuit_equivalence b/circuit_equivalence
@@ -1,5 +1,5 @@
# Circuit equivalence
-[Computational_problem] of deciding, given two [Boolean_circuits], whether they represent the same [Boolean_function]
+The [computational_problem] of deciding, given two [Boolean_circuits], whether they represent the same [Boolean_function]
-Up: [equivalence], [circuit]
+Up: [Boolean_function_equivalence], [circuit]
diff --git a/decision_tree b/decision_tree
@@ -0,0 +1,13 @@
+# Decision tree
+
+A way to represent a [Boolean_function]
+
+Generalization: [bdd]
+
+The [boolean_function_equivalence] problem on decision trees can be solved in [quadratic] time, cf [cockett1987discrete] and [zantema1998equivalence]
+
+Up: [knowledge_compilation_formalisms]
+
+Aliases: decision trees
+
+See also: [tree]
diff --git a/equivalence_problem b/equivalence_problem
@@ -4,7 +4,8 @@
- [query_equivalence]
- [automaton_equivalence]
- [regular_expression_equivalence]
-- [circuit_equivalence]
+- [Boolean_function_equivalence]
+ - [circuit_equivalence]
Up: [computational_problem], [equivalence]
diff --git a/knowledge_compilation_classes b/knowledge_compilation_classes
@@ -20,7 +20,7 @@
- [fbdd]
- [zero_suppressed_semantics]
-Up: [knowledge_compilation], [circuit]
+Up: [knowledge_compilation], [circuit], [Boolean_function_representation]
See also: [circuit_classes], [circuit_condition]
