commit 09c2241c08298613ec2612d16f50be0a02f0c6b7
parent 44ef4508b68a0b075fe6c47a6bd7766436947b4d
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 26 May 2026 10:43:23 +0200
commit with codex
Diffstat:
17 files changed, 71 insertions(+), 18 deletions(-)
diff --git a/1_planar_graph b/1_planar_graph
@@ -0,0 +1,7 @@
+# 1 planar graph
+
+https://en.wikipedia.org/wiki/1-planar_graph
+
+Different from [crossing_number]: every [edge] has at most one crossing
+
+Up: [planar_graph]
diff --git a/bdd b/bdd
@@ -10,3 +10,5 @@
Up: [diagram]
See also: [branching_program], [read_once_branching_program], [decision_tree], [read_twice_branching_program]
+
+Aliases: binary decision diagram, binary decision diagrams, BDDs
diff --git a/boundary_operation b/boundary_operation
@@ -0,0 +1,9 @@
+# Boundary operation
+
+the *boundary* of a [language] L is L^* cap (L^c)^*
+
+studied, e.g., in [jirasek2026boundary]
+
+Up: [formal_language_operator]
+
+See also: [kleene_star], [language_complement], [language_intersection]
diff --git a/circuit_equivalence_ddnnfs b/circuit_equivalence_ddnnfs
@@ -1,5 +1,9 @@
# Circuit equivalence d-DNNFs
-It is in [coRP]: [darwiche2002testing]
+The [circuit_equivalence_problem] on [d-DNNFs] is in [coRP]: [darwiche2002testing]
-Up: [circuit_equivalence], [d-DNNF]
+Up: [circuit_equivalence_problem], [d-DNNF]
+
+Aliases: dDNNF_equivalence
+
+See also: [polynomial_identity_testing]
diff --git a/circuit_multivalued b/circuit_multivalued
@@ -12,6 +12,6 @@ Enforcing [circuit_structuredness], or enforcing [circuit_determinism], results
Up: [circuit]
-See also: [Factorized_database], [multivalued_formula]
+See also: [Factorized_database], [multivalued_formula], [multivalued_decision_diagram]
Aliases: multivalued circuit, multivalued circuits
diff --git a/crossing_number b/crossing_number
@@ -14,4 +14,4 @@ The crossing number of [complete_bipartite_graphs] is an [open_problem], cf http
Up: [planar_graph]
-See also: [single_crossing_graph]
+See also: [single_crossing_graph], [1_planar_graph]
diff --git a/diagram b/diagram
@@ -13,6 +13,6 @@
Up: [knowledge_compilation_classes]
-See also: [read_once], [decision_tree]
+See also: [read_once], [decision_tree], [zero_suppressed_semantics]
Aliases: decision diagram, decision diagrams, diagrams
diff --git a/formal_language_operator b/formal_language_operator
@@ -18,6 +18,7 @@ An [operator] that takes one or two [formal_languages] and creates a new [formal
- [formal_language_closure_operation]: an operator that takes one [formal_language] and extends it by adding more [words] to it
- [upward_closure] / [downward_closure]
- [commutative_closure]
+- [boundary_operation]
Up: [formal_language], [operator]
diff --git a/graph_family b/graph_family
@@ -47,6 +47,8 @@ A (generally [infinite]) set of [graphs]
- [unit_distance_graph]
+- [graph_word_representable]
+
May have the property of being [graph_class_hereditary]
Up: [graph]
diff --git a/grid_graph b/grid_graph
@@ -6,6 +6,6 @@
Up: [graph_family]
-See also: [wall_graph]
+See also: [wall_graph], [grid_embedding]
Aliases: grid graphs, grid
diff --git a/knowledge_compilation_classes b/knowledge_compilation_classes
@@ -1,15 +1,20 @@
# Knowledge compilation classes
-- [decomposable] [dnnf]
-- [sdnnf], with [structuredness]
-- [ddnnf], with [deterministic]
+- [negation_normal_form]
+- [decomposability]
+ - [DNNF]
+ - [wDNNF]
+- [structuredness]
+ - [SDNNF]
+- [circuit_determinism]: [d-DNNF]
- exponentially separated from [dnnf]
- [sauerhoff_function]
- [ordered_dnnf], in [amarilli2017circuit]
-- [smoothing]
-- [sdd]
+- [smoothness]
+- [SDD]
- exponentially separated from [obdd]
- [hidden_weighted_bit_function]
+- [TDD]
- [decision_dnnf]
- [decision_sdnnf]
- [ordered_decision_circuit]
@@ -18,7 +23,7 @@
- [nobdd]
- [uobdd]
- [fbdd]
- - [zero_suppressed_semantics]
+ - see also: [zero_suppressed_semantics]
Up: [knowledge_compilation], [circuit], [Boolean_function_representation]
diff --git a/lower_bounds b/lower_bounds
@@ -5,6 +5,6 @@
Up: [computational_complexity]
-See also: [theorem], [upper_bound]
+See also: [theorem], [upper_bound], [lower_bound_techniques]
Aliases: lower bound
diff --git a/negation_normal_form b/negation_normal_form
@@ -0,0 +1,15 @@
+# Negation normal form
+
+[Boolean_circuits] using [OR], [AND], [literal_gates], and [cosntant_gates]
+
+Hence, [negation] is only at the leaves
+
+Subclasses:
+
+- [DNNF]
+
+All [knowledge_compilation_queries] are (conditionally) intractable on the class ; some [knowledge_compilation_transformations] are tractable and others not
+
+Up: [knowledge_compilation_classes]
+
+Aliases: NNF
diff --git a/obdd b/obdd
@@ -8,7 +8,11 @@ A [deterministic] [bdd] with a [variable_order]
We can tractably take the [conjunction] and [disjunction] of two OBDDs where the [variable_order] is the same
- [OBDD_conjunction]
-Generalization: [CFLOBDDs]
+Generalizations:
+- [CFLOBDDs]
+- [FBDDs]
+
+Notion: [bdd_width]
Up: [bdd]
diff --git a/planar_graph b/planar_graph
@@ -32,10 +32,12 @@ Generalizations:
- to [hypergraphs]: [planar_hypergraph]
- to [directed_graphs]: [directed_planar_graph]
-- to quantify the "degree of non-planarity": [crossing_number]
-- [single_crossing_graph]
+- to quantify the "degree of non-planarity":
+ - [crossing_number]
+ - [single_crossing_graph]
+ - [1_planar_graph]
-See also: [graph_drawing], [planar_separator_theorem]
+See also: [graph_drawing], [planar_separator_theorem], [grid_embedding]
Up: [graph]
diff --git a/structuredness b/structuredness
@@ -11,4 +11,4 @@ A [Boolean_circuit] in [DNNF] that has a [vtree]
Up: [circuit_condition]
-Aliases: structured circuit, structured, structured circuits, circuit structuredness
+Aliases: structured circuit, structured, structured circuits, circuit structuredness, structured decomposability
diff --git a/vtree b/vtree
@@ -5,3 +5,5 @@ A [tree] on the [variables] of a [circuit], used to define [structuredness]
Up: [tree], [knowledge_compilation]
See also: [variable_order]
+
+Aliases: vtrees
