commit b85411800c4ccc628dfbf098057fa73fa38a2bd4
parent b510c2253ebd05b7e1f364e06ebef5b46cb92577
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 12 Sep 2025 07:22:32 +0200
commit with codex
Diffstat:
23 files changed, 134 insertions(+), 9 deletions(-)
diff --git a/amarilli2024tractable b/amarilli2024tractable
@@ -0,0 +1,8 @@
+# amarilli2024tractable
+
+- [circuit_multivalued]
+ - [union_product_circuit]
+ - [disjoint_union_product_circuit]
+ - [union_join_circuit]
+
+Up: [survey] on [database_theory_circuits]
diff --git a/automata_complementation b/automata_complementation
@@ -4,7 +4,7 @@
- exponential lower bound on [state_complexity] for [automata_nondeterministic]
- hard also for [word_automaton_unambiguous]
-Up: [complementation], [automata]
+Up: [automaton_constructions], [complementation]
Aliases: automaton complement, automaton complementation
diff --git a/automata_constructions b/automata_constructions
@@ -9,6 +9,6 @@
- [product_automaton], for [automaton_intersection]
- [automaton_trimming] / [automaton_completion]
-Up: [automata]
+Up: [automata], [constructions]
Aliases: automaton construction, automaton constructions
diff --git a/boolean_circuit b/boolean_circuit
@@ -4,6 +4,7 @@ Expresses [boolean_function]
- [circuit_complexity]
- [circuit_condition]
+- [circuit_operation]
Similar: https://en.wikipedia.org/wiki/Propositional_directed_acyclic_graph
diff --git a/circuit b/circuit
@@ -6,6 +6,7 @@
- [knowledge_compilation_classes]
- [circuit_complexity]
- [circuit_classes]
+- [database_theory_circuits]
## Types
diff --git a/circuit_condition b/circuit_condition
@@ -1,10 +1,12 @@
# Circuit condition
-Conditions that can be posed on [circuit]
+Conditions that can be posed on [circuits]
- [decomposability]
- [deterministic]
- [structuredness] (e.g., [vtree])
+- [constant_free], can be enforced by propagating constants unless the circuit computes a constant
+- [smooth]
Up: [circuit]
diff --git a/circuit_equivalence_ddnnfs b/circuit_equivalence_ddnnfs
@@ -0,0 +1,5 @@
+# Circuit equivalence d-DNNFs
+
+It is in [coRP]: [darwiche2002testing]
+
+Up: [circuit_equivalence], [d-DNNF]
diff --git a/circuit_multivalued b/circuit_multivalued
@@ -0,0 +1,17 @@
+# Circuit multivalued
+
+Variants of [Boolean_circuits] defined in a multivalued fashion, see [amarilli2024tractable]
+
+- [union_product_circuit]
+- [disjoint_union_product_circuit]
+- [union_join_circuit]
+
+Circuits can be made [constant_free] by propagating away constants, unless they represent the empty set or the complete set
+
+Enforcing [circuit_structuredness], or enforcing [circuit_determinism], results in an exponential blowup: cf [vinallsmeeth2025how] Example 2.12
+
+Up: [circuit]
+
+See also: [Factorized_database], [multivalued_formula]
+
+Aliases: multivalued circuit, multivalued circuits
diff --git a/circuit_operation b/circuit_operation
@@ -0,0 +1,9 @@
+# Circuit operation
+
+- [circuit_restriction]: project away some variables
+- [circuit_selection]: for [multivalued_circuits], restrict the values to be in a subset of the domain
+- [circuit_complementation]
+- [circuit_disjunction]
+- ensure that all [gates] have [fan_in] 2
+
+Up: [constructions] on [boolean_circuit]
diff --git a/circuit_trace b/circuit_trace
@@ -2,4 +2,10 @@
cf [rodriguesalves2021succinct], which studies [succinct_monotone_circuit_certification] problem
+Also known as "parse tree" or "certificate" or "proof tree"
+
Up: [circuit]
+
+See also: [parse_tree], [proof_tree]
+
+Aliases: certificate
diff --git a/constructions b/constructions
@@ -0,0 +1,6 @@
+# Constructions
+
+- [automata_constructions]
+- [circuit_constructions]
+
+Up: [mathematics]
diff --git a/curticapean2014complexity b/curticapean2014complexity
@@ -0,0 +1,5 @@
+# curticapean2014complexity
+
+[academic_paper] on [subgraph_counting_problem]
+
+Up: [academic_paper]
diff --git a/database_theory_circuits b/database_theory_circuits
@@ -0,0 +1,5 @@
+# Database theory circuits
+
+[survey]: [amarilli2024tractable]
+
+Up: [circuit], [database_theory]
diff --git a/decision b/decision
@@ -1,6 +1,8 @@
# Decision
-Used in [diagram], also in [decision_dnnf]
+The use of [decision_gate]
+
+Used in [diagrams], also in [decision_dnnf]
other name: "syntactic unambiguity"
diff --git a/decision_dnnf b/decision_dnnf
@@ -1,10 +1,10 @@
# Decision-DNNF
-[dnnf] but only with [decision] gates
+A *decision-DNNF* is a [DNNF] but only with [decision_gates]
- special case: [ordered_decision_circuit]
- special case: [decision_sdnnf]
Up: [dnnf]
-Aliases: decision_DNNFs, decision-DNNF, decision-DNNFs
+Aliases: decision_DNNFs, decision-DNNF, decision-DNNFs, decDNNF, decDNNFs
diff --git a/decision_gate b/decision_gate
@@ -0,0 +1,12 @@
+# Decision gate
+
+A gate that tests the value of a variable
+
+Used in [diagrams] and in [circuit_classes] like [decDNNF]
+
+In [vinallsmeeth2025how], [generalized_decision_gate]
+- uses a [partition] of the assignments
+
+Up: [decision]
+
+Aliases: decision gates
diff --git a/deque b/deque
@@ -0,0 +1,7 @@
+# Deque
+
+Can be simulated with O(1) [stacks], cf [hood1980real]
+
+See also: [queue]
+
+Up: [data_structure]
diff --git a/diagram b/diagram
@@ -15,4 +15,4 @@ Up: [knowledge_compilation_classes]
See also: [read_once], [decision_tree]
-Aliases: decision diagram, decision diagrams
+Aliases: decision diagram, decision diagrams, diagrams
diff --git a/disjoint_union_product_circuit b/disjoint_union_product_circuit
@@ -0,0 +1,13 @@
+# Disjoint union product circuit
+
+A [circuit] built using [disjoint_union] and [cartesian_product] gates
+- may be assumed to be [smooth] or not
+- if not, the [disjoint_union] is extended to complete the missing positions
+
+Is the [circuit_multivalued] analogue of [d-DNNFs]
+
+Defined in [amarilli2024tractable]
+
+Up: [circuit_multivalued]
+
+Aliases: disjoint union times circuit, disjoint union times circuits, disjoint union product circuits
diff --git a/queue b/queue
@@ -5,4 +5,4 @@
Up: [data_structure]
-See also: [stack]
+See also: [stack], [deque]
diff --git a/structuredness b/structuredness
@@ -6,4 +6,4 @@ A [Boolean_circuit] in [DNNF] that has a [vtree]
Up: [circuit_condition]
-Aliases: structured circuit, structured, structured circuits
+Aliases: structured circuit, structured, structured circuits, circuit structuredness
diff --git a/union_join_circuit b/union_join_circuit
@@ -0,0 +1,13 @@
+# Union join circuit
+
+A [circuit] built using [union] and [relational_join] gates
+- may be assumed to be [smooth] or not
+- if not, the [union] is extended to complete the missing positions
+
+Is the [circuit_multivalued] analogue of [NNFs]
+
+Defined in [amarilli2024tractable]
+
+Up: [circuit_multivalued]
+
+Aliases: union join circuit, union join circuits, union join circuits
diff --git a/union_product_circuit b/union_product_circuit
@@ -0,0 +1,13 @@
+# Union product circuit
+
+A [circuit] built using [union] and [cartesian_product] gates
+- may be assumed to be [smooth] or not
+- if not, the [union] is extended to complete the missing positions
+
+Is the [circuit_multivalued] analogue of [DNNFs]
+
+Defined in [amarilli2024tractable]
+
+Up: [circuit_multivalued]
+
+Aliases: union times circuit, union times circuits, union product circuits
