commit 45912a9fcde25b5b14eec3514b9901180163bd0e
parent 467551373fbee6ede51492952be990ab6c0c4956
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 27 May 2026 11:55:28 +0200
commit with codex
Diffstat:
11 files changed, 31 insertions(+), 6 deletions(-)
diff --git a/automata_alternating b/automata_alternating
@@ -12,4 +12,4 @@ Up: [automata_types]
Aliases: alternating automaton, alternating automata
-See also: [alternating_turing_machine]
+See also: [alternating_turing_machine], [tree_automata_alternating]
diff --git a/automata_reversible b/automata_reversible
@@ -11,6 +11,6 @@ Class of [formal_language] accepted by a reversible automaton
- membership given an [automata] can be tested in [ptime]
- [pin1992reversible]
-See also: [turing_machine_symmetric], [automata_symmetric], [transducer_reversible]
+See also: [turing_machine_symmetric], [automata_symmetric], [transducer_reversible], [circuit_reversible]
Up: [word_automaton]
diff --git a/bayes_network b/bayes_network
@@ -7,3 +7,5 @@ Can be "tree-structured Bayes network", or have bounded [treewidth]
Up: [probabilistic_graphical_model]
See also: [message_passing], [treewidth]
+
+Aliases: bayesian network, bayesian networks, bayes networks
diff --git a/circuit_algebraic b/circuit_algebraic
@@ -5,3 +5,5 @@
Up: [probabilistic_circuit], [algebra]
Aliases: algebraic circuit, algebraic circuits
+
+See also: [algebraic_decision_diagram]
diff --git a/graph_packing b/graph_packing
@@ -12,6 +12,8 @@ Can be with [induced_subgraphs] (a "strict factor")
[kirkpatrick1983complexity]: the packing problem with [induced_subgraphs] when the [graph] to pack has at least 3 vertices is [NP_complete]
+[hell1986packings], includes packings by [stars]
+
Up: [computational_problem] on [graph]
See also: [packing_problem], [graph_partition], [path_cover], [path_partition]
diff --git a/guarded_fixpoint_logic b/guarded_fixpoint_logic
@@ -2,6 +2,8 @@
Does not have the [finite_model_property], see [barany2012finite]
+Generalizations: [GNFP]
+
Up: [guarded_fragment], [fixpoint]
Aliases: muGF
diff --git a/probabilistic_graphical_model b/probabilistic_graphical_model
@@ -1,6 +1,7 @@
# Probabilistic graphical model
- [bayes_network]
+- [markov_network]
- [markov_logic_network]
- [sum_product_network]
diff --git a/satisfiability_weighted_ddnnf_negation b/satisfiability_weighted_ddnnf_negation
@@ -1,10 +1,19 @@
# Satisfiability weighted ddnnf negation
-The [computational_problem] of deciding whether a [dDNNF] has a [falsifying_assigment] of a given weight?
+The [computational_problem] of deciding whether a [dDNNF] has a [falsifying_assigment] of at least a given weight
+- weight is given as a weight on each literal
+- up to renormalization, up to negation
+ - 0 has weight 0
+ - 1 has positive weight
-Already challenging for [orthogonal_DNF], cf [satisfiability_weighted_orthogonal_DNF_negation]
+In the absence of weight this is [satisfiability_dnnnf_negation] which can be done thanks to [counting]
+
+It is tractable when weights are written in [unary], by [dynamic programming]: we know how many assignments there are of each weight, and how many satisfying assignments there are on each weight
-But tractable when weights are written in [unary]
+We can do [satisfiability_weighted_ddnnf] of deciding whether there is an assignment of at least this weight, by storing the maximum weight
+- of course exact weight is [NP_hard] by reduction from [subset_sum]
+
+Already challenging for [orthogonal_DNF], cf [satisfiability_weighted_orthogonal_DNF_negation]
Related to [ddnnf_complementation]
diff --git a/sharp_nfa b/sharp_nfa
@@ -17,3 +17,5 @@
Up: [sharp_automaton], [automata_nondeterministic]
See also: [sharp_dfa], [sharp_cfg]
+
+Aliases: sharpNFA
diff --git a/st_reliability b/st_reliability
@@ -2,7 +2,9 @@
The case of [network_reliability] with a fixed source and target
-Can be posed on [directed_graphs] and [undirected_graphs]
+Can be posed:
+- on [directed_graphs]: [st_reliability_directed]
+- on [undirected_graphs]: [st_reliability_undirected]
- [st_reliability_approximation]
- [st_reliability_provenance]
diff --git a/tree_automaton b/tree_automaton
@@ -9,6 +9,9 @@ Defines [regular_tree_language]
- [tree_automaton_top_down]
- [tree_automaton_deterministic]
- [tree_automaton_nondeterministic]
+- [tree_automaton_two_way]
+- [tree_automaton_alternating]
+- [tree_automaton_two_way_alternating]
## Variants
