commit c9d2397ef33b6a1dc0a4c9de441b79069b6f8e7f
parent faee1ed3fc0546fd171f4a195f528caacd3a9ea6
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 11 Jun 2026 14:26:44 +0200
commit with codex
Diffstat:
15 files changed, 35 insertions(+), 16 deletions(-)
diff --git a/2cnf b/2cnf
@@ -3,9 +3,12 @@
A [conjunctive_normal_form] [boolean_formula] where every [clause] contains two [literals]
- [satisfiability_boolean] on such formulas: [2sat]
+- [sharp_sat] on such formulas: [sharp_2cnf] / [sharp_monotone2cnf]
- generalization: [kcnf]
- special case: [monotone2cnf]
Compilation to [OBDDs], cf [decolnet2026compilability] with [phase_transitions]
Up: [conjunctive_normal_form]
+
+See also: [2DNF]
diff --git a/berkholz2017answering b/berkholz2017answering
@@ -5,6 +5,8 @@
[academic_paper] by [christoph_berkholz], [jens_keppeler], [nicole_schweikardt]
- [q_hierarchical]: [CQs] for which an [enumeration_constant_delay] [data_structure] can be [maintained_under_updates]
+- [t_hierarchical]
+- [exhaustively_q_hierarchical]
- [lower_bounds] assuming [omv_conjecture]
Up: [incremental_maintenance_enumeration]
diff --git a/computational_problem b/computational_problem
@@ -43,4 +43,4 @@
Up: [theoretical_computer_science]
-Aliases: computational problems, computation problem
+Aliases: computational problems, computation problem, computational task, computation task, computational tasks, computation tasks
diff --git a/courcelle_theorem b/courcelle_theorem
@@ -10,6 +10,8 @@ time f(|phi|, width) times linear in the graph
[courcelle_logspace]
+The query dependency is [nonelementary], but for [FO] on [pathlike_data] it is [elementary], cf [lampis2026first]
+
Up: [theorem] on [monadic_second_order_logic_model_checking], [algorithmic_metatheorem]
Aliases: Courcelle's theorem
diff --git a/disjunctive_normal_form b/disjunctive_normal_form
@@ -2,6 +2,7 @@
A [Boolean_formula] which is a [disjunction] of [terms]
+- [2dnf]
- [pp2dnf]
- [disjunctive_normal_form_orthogonal]
diff --git a/minimum_equivalent_dnf b/minimum_equivalent_dnf
@@ -8,6 +8,6 @@ Generalization to arbitrary [Boolean_formulas] (and also to bounded-depth [Boole
Related problem via [truth_tables] on [Boolean_formulas] ([Minimum_formula_size_problem]) and [Boolean_circuits] ([MCSP])
-See also: [umans2001minimum], [DNF_minimization], [goldsmith2008complexity]
+See also: [umans2001minimum], [DNF_minimization], [goldsmith2008complexity], [shortest_implicant]
Up: [minimum_equivalent_problem], [DNF]
diff --git a/monotone2cnf b/monotone2cnf
@@ -1,9 +0,0 @@
-# monotone2cnf
-
-A [monotone_CNF] which is a [2CNF]
-
-- [monotone2CNF_SAT]
-
-Up: [monotone_CNF], [2CNF]
-
-Aliases: monotone_2_CNF, monotone_2CNF
diff --git a/partial_word b/partial_word
@@ -1,9 +1,11 @@
# Partial word
-A [word] where some positions are specified and others are [don't_cares]
+A *partial word* is a [word] where some positions are specified and others are filled with [don't_cares]
Studied in [berstel1999partial] and in [amarilli2026complexity]
+An [extension] is a completion of the partial word
+
Up: [word]
See also: [probabilistic_word]
diff --git a/pathlike b/pathlike
@@ -0,0 +1,9 @@
+# Pathlike
+
+"of bounded [pathwidth]"
+
+- [pathlike_data]
+
+Up: [pathwidth]
+
+See also: [treelike]
diff --git a/pathwidth b/pathwidth
@@ -14,4 +14,4 @@ like [treewidth] but for [tree_decomposition] which is a [path]
Up: [width_measure], [path]
-See also: [treewidth], [path_excentricity], [treelength]
+See also: [treewidth], [path_excentricity], [treelength], [pathlike]
diff --git a/probabilistic_membership_problem b/probabilistic_membership_problem
@@ -6,6 +6,6 @@ Studied in [amarilli2026complexity]
Up: [membership_problem], [PQE]
-See also: [Pattern_matching_dontcare_pqe]
+See also: [Pattern_matching_dontcare_pqe], [counting_extensions], [partial_word]
-Aliases: formal language membership pqe, membership problem pqe
+Aliases: formal language membership pqe, membership problem pqe, probabilistic membership
diff --git a/treelike b/treelike
@@ -11,3 +11,5 @@
Up: [treewidth]
Aliases: bounded treewidth
+
+See also: [pathlike]
diff --git a/treelike_data b/treelike_data
@@ -6,4 +6,4 @@ On such data we can do [pqe_mso]
Up: [data] of bounded [treewidth], [types_of_data]
-See also: [bounded_treewidth_graph]
+See also: [bounded_treewidth_graph], [pathlike_data]
diff --git a/tuple_testing b/tuple_testing
@@ -6,6 +6,11 @@ Testing if an input tuple is a solution to a [query]
- [rpq_answer_testing]
- [incremental_maintenance_tuple_testing]
+Generalizations:
+
+- [rank_unrank]
+- [counting_extensions]
+
See also: [dynamic_data], [enumeration], [enumeration_extensions]
Up: [database_theory]
diff --git a/umans2001minimum b/umans2001minimum
@@ -2,6 +2,8 @@
studies the [minimum_equivalent_DNF] problem and shows that it is [Sigma_p_2_complete]
+also studies [shortest_implicant]
+
See also: [minimum_formula_size_problem], [goldsmith2008complexity]
Up: [Academic_paper]
