commit 90f60c2652cfb477c84837d964fb698375f2e071
parent e5e860848ad5eb239e41ecc28c04cdf960a19443
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 16 Mar 2026 15:31:12 +0100
Merge remote-tracking branch 'origin/master'
Diffstat:
31 files changed, 148 insertions(+), 15 deletions(-)
diff --git a/1_or_3_in_3_sat b/1_or_3_in_3_sat
@@ -10,4 +10,4 @@ Up: [schaefers_dichotomy_theorem], [sat_variants]
Aliases: 1 or 3 in 3SAT
-See also: [xor_sat]
+See also: [xor_sat], [1_in_3_SAT]
diff --git a/aho_corasick b/aho_corasick
@@ -1,6 +1,6 @@
# Aho Corasick
-A nice algorithm to build an [automaton] for efficient [pattern_matching] with a dictionary.
+A nice algorithm to build an [automaton] for efficient [dictionary_matching]
Up: [pattern_matching]
diff --git a/backurs2016which b/backurs2016which
@@ -1,9 +1,13 @@
# Backurs2016which
-uses [strong_exponential_time_hypothesis] and [orthogonal_vectors]
+lower bound using [strong_exponential_time_hypothesis] and [orthogonal_vectors]
+
+classification of [homogeneous_regular_expressions]
[follow_up]: [bringmann2016dichotomy]
Up: [academic_paper] on [regular_expression_matching]
-See also: [Ov_to_regular_expression_matching], [backurs_indyk]
+See also: [Ov_to_regular_expression_matching], [word_break_problem]
+
+Aliases: Backurs Indyk
diff --git a/context_free_language_complement b/context_free_language_complement
@@ -4,6 +4,8 @@ A [formal_language] which is the [language_complementation] of a [CFL]
[Emptiness_testing] is [undecidable] because the [universality_problem] is [undecidable] for [CFLs]
+The [language_complement] of a [CFL] or even a [UCFL] may not be a [CFL], cf https://mathoverflow.net/questions/163517/is-there-an-unambiguous-cfl-whose-complement-is-not-context-free
+
Up: [language_complementation], [CFL]
Aliases: CFG complement, CFL complement
diff --git a/decision_dnnf b/decision_dnnf
@@ -5,6 +5,8 @@ A *decision-DNNF* is a [DNNF] but only with [decision_gates]
- special case: [ordered_decision_circuit]
- special case: [decision_sdnnf]
+See [cali2026complexity]
+
Up: [dnnf]
Aliases: decision_DNNFs, decision-DNNF, decision-DNNFs, decDNNF, decDNNFs
diff --git a/dictionary_matching b/dictionary_matching
@@ -0,0 +1,7 @@
+# Dictionary matching
+
+The generalization of the [pattern_matching] problem to the case where you have a dictionary of patterns
+
+[Algorithm] for this: [aho_corasick]
+
+Up: [computational_problem], [stringology]
diff --git a/functional_dependency b/functional_dependency
@@ -27,3 +27,5 @@
Up: [equality_generating_dependency]
Aliases: FD, FDs, functional dependencies
+
+See also: [functional_digraph]
diff --git a/functional_digraph b/functional_digraph
@@ -0,0 +1,10 @@
+# Functional digraph
+
+Also called a "directed pseudoforest"
+- cf https://en.wikipedia.org/wiki/Pseudoforest#Directed_pseudoforests
+
+paper: [bridoux2026dividing]
+
+See also: [enumeration_walk_blit]
+
+Aliases: directed pseudoforest, directed pseudoforests, functional digraphs, functional graph, functional graphs
diff --git a/hypergraph b/hypergraph
@@ -27,6 +27,10 @@ generalizes [graph]
- [hyperclique_detection] / [hyperclique_hypothesis]
+## Variants
+
+- [hypergraph_directed]
+
See also: [generalized_hypertree_width], [conjunctive_query], [relational_instance], [simplicial_complex], [Hyperedge_replacement_grammar]
Up: [data_structure], [computer_science]
diff --git a/hypergraph_directed b/hypergraph_directed
@@ -0,0 +1,9 @@
+# Directed hypergraph
+
+A [hypergraph] where each [hyperedge] contains head vertices and tail vertices
+
+Up: [hypergraph]
+
+See also: [relational_signature]
+
+Aliases: directed hypergraph, directed hypergraphs
diff --git a/hyperpath_width b/hyperpath_width
@@ -0,0 +1,5 @@
+# Hyperpath width
+
+discussed in [adler2012hypertree]
+
+Up: [hypertree_width_variants], [pathwidth]
diff --git a/hypertree_width_variants b/hypertree_width_variants
@@ -6,3 +6,5 @@
- [query_decomposition]
Up: [width_measure] for [hypergraph]
+
+See also: [hyperpath_width]
diff --git a/knowledge_compilation_classes b/knowledge_compilation_classes
@@ -24,4 +24,4 @@ Up: [knowledge_compilation], [circuit], [Boolean_function_representation]
See also: [circuit_classes], [circuit_condition]
-Aliases: knowledge compilation circuit classes
+Aliases: knowledge compilation circuit classes, knowledge compilation circuits
diff --git a/logspace b/logspace
@@ -1,6 +1,6 @@
# L
-Class of problems that can be solved with logarithmic space [complexity_space]
+Class of problems that can be solved with logarithmic [complexity_space]
Is included in [PTIME]
@@ -13,4 +13,4 @@ Variant [SL]: symmetric logspace, class of problems reducible to undirected [rea
Up: [complexity_class]
-Aliases: L
+Aliases: L, deterministic logspace
diff --git a/mod_k_p b/mod_k_p
@@ -8,4 +8,4 @@ For k=2, [parity_p]
Up: [parity_p]
-See also: [modular_counting]
+See also: [modular_counting], [sharp_k_p]
diff --git a/multigraph_directed b/multigraph_directed
@@ -0,0 +1,9 @@
+# Directed multigraph
+
+#todo
+
+Up: [multigraph], [directed_graph]
+
+Aliases: directed multigraph, directed multigraphs
+
+See also: [undirected_multigraph]
diff --git a/multigraph_undirected b/multigraph_undirected
@@ -0,0 +1,9 @@
+# Undirected multigraph
+
+#todo
+
+Up: [multigraph], [undirected_graph]
+
+Aliases: undirected multigraph, undirected multigraphs
+
+See also: [directed_multigraph]
diff --git a/nlogspace b/nlogspace
@@ -1,6 +1,6 @@
# NL
-[complexity_class] of [decision_problems] that can be solved by [nondeterministic] [turing_machine] with [logarithmic] amount of memory
+[complexity_class] of [decision_problems] that can be solved by [nondeterministic_turing_machine] with [logarithmic] amount of memory
Like [logspace] with [nondeterministic]
@@ -17,4 +17,4 @@ Up: [complexity_class]
See also: [nl_complete]
-Aliases: NL
+Aliases: NL, nondeterministic logspace
diff --git a/one_bit_catastrophe b/one_bit_catastrophe
@@ -0,0 +1,7 @@
+# One bit catastrophe
+
+cf [lagarde2017lempel]
+
+Up: [lz78]
+
+See also: [lz77]
diff --git a/path b/path
@@ -8,6 +8,7 @@ sequence of vertices in a [graph] such that any two successive vertices are conn
- [hamiltonian_path]
- [eulerian_path]
- [path_undirected]
+- [path_directed]
Up: [graph]
diff --git a/path_directed b/path_directed
@@ -0,0 +1,9 @@
+# Directed path
+
+A [path] in a [directed_graph]
+
+Up: [path]
+
+Aliases: directed path, directed paths
+
+See also: [undirected_path]
diff --git a/pattern_matching b/pattern_matching
@@ -33,11 +33,12 @@
- [pattern_matching_compressed] on [compressed_data]
- [gapped_pattern_matching]: find two patterns separated by a distance within a specified range
- [text_index], when the text can be preprocessed
+- [dictionary_matching]
## Implementations
- [pattern_matching_practice]
-Up: [stringology]
+Up: [stringology], [computational_problem]
See also: [pattern], [pattern_matching_2d]
diff --git a/probabilistic_membership_problem b/probabilistic_membership_problem
@@ -5,3 +5,7 @@ Having fixed a [formal_language], given a [probabilistic_word], what is the prob
Studied in [amarilli2026complexity]
Up: [membership_problem], [PQE]
+
+See also: [Pattern_matching_dontcare_pqe]
+
+Aliases: formal language membership pqe, membership problem pqe
diff --git a/probabilistic_word b/probabilistic_word
@@ -2,8 +2,6 @@
A [word] where each position specifies a [probability_distribution] on letters
-Studied in [amarilli2026complexity]
-
- [probabilistic_membership_problem]
Related work, cf [probabilistic_word_related_work]:
diff --git a/property_testing b/property_testing
@@ -1,9 +1,36 @@
# Property testing
+You have an object O and a property P, and you want to determine if O has property P via local queries. Further, you have the promise that O either has the property P, or is ε-far from the property, i.e., the distance from O to any object X having the property is at least ε |X|. You want to minimize the [query_complexity]
+
+Examples:
+
- [property_testing_formal_language]
+ - you want to test membership to a [formal_language]
+ - you can test which letter is at a given position
+ - the promise is on some proportion of the letters in the word
+- [property_testing_Boolean_function]
+ - you want to test if a [Boolean_function] has a certain property
+ - is it a [constant_boolean_function]
+ - is it a [dictatorship_boolean_function]
+ - you can evaluate the function at some point
+ - the promise is on some proportion of the values of the truth table
+- [property_testing_graph]
+ - you want to test a [graph_property]
+ - you can test whether some edge exists (dense graphs) or find the i-th neighbor of a vertex (sparse graphs of bounded degree)
+ - the promise is in some proportion of the values of the [adjacency_matrix] (dense graphs) or edges (sparse graphs)
- [property_testing_CSP]
- [property_testing_databases]
+Typical framework:
+
+- local obstructions that justify that you don't have the property
+ - e.g., a [triangle] in a graph, when determining if the graph is [triangle_free]
+ - e.g., x and y such that f(x) \neq f(y), when determining if a function is constant
+- lemma: ε-far => contains many obstructions
+ - e.g., a graph which is ε-far from a triangle-free graph contains many triangles
+ - [Szemerédi's_Regularity_Lemma]
+- sampling algorithm to find a local obstruction whp
+
Up: [computational_problem]
See also: [model_checking], [Approximate_membership], [tolerant_property_testing]
diff --git a/query_resilience b/query_resilience
@@ -53,6 +53,8 @@ Generalization:
- [deletion_propagation_with_source_side_effects]
+Introduced in: [meliou2010complexity]
+
Old related work: [yannakakis1981edge]
Up: [database_theory]
diff --git a/regular_expression_matching_sliding_window b/regular_expression_matching_sliding_window
@@ -0,0 +1,7 @@
+# Regular expression matching sliding window
+
+[academic_papers]: [ganardi2022low], [ganardi2024regular]
+
+Up: [sliding_window], [Regular_expression_matching]
+
+Aliases: regular language membership sliding window, regular language matching sliding window, regular expression membership sliding window
diff --git a/sjfcq b/sjfcq
@@ -10,4 +10,4 @@ Special cases:
Up: [conjunctive_query], [self_join]
-Aliases: self join free CQ, self join free CQs, selfjoin free CQ, selfjoin free CQs, cq self join free, cqs self join free, self-join-free CQ, self-join-free CQs, conjunctive query self join free, SJFCQs
+Aliases: self join free CQ, self join free CQs, selfjoin free CQ, selfjoin free CQs, cq self join free, cqs self join free, self-join-free CQ, self-join-free CQs, conjunctive query self join free, SJFCQs, self join free query, self join free queries
diff --git a/strahler_number b/strahler_number
@@ -9,6 +9,10 @@ cf [esparza2016brief]
Related to [pathwidth] by a factor of 2
- cf https://en.wikipedia.org/wiki/Strahler_number#Pathwidth
+The height of the largest [perfect_binary_tree] that can be [tree_embedded] into t
+
Up: [parameter] on [tree]
See also: [cantor_bendixson_rank], [ganardi2025complexity]
+
+Aliases: Strahler numbers
diff --git a/tree_evaluation_problem b/tree_evaluation_problem
@@ -2,10 +2,15 @@
You have a [tree] and you want to evaluate a [bottom_up_nondeterministic_tree_automaton] on the tree, in a [nonuniform] sense where each [node] is labeled by the transition function
+Covers in particular the evaluation of [Boolean_formulas] and the acceptance of a fixed [tree_automaton]
+
+Sometimes considered specifically on [complete_binary_trees] and on functions at the nodes given as input.
+
It is in O(log n log log n), cf [cook2023tree] and [goldreich2024cook]
+=> leading to [williams2025simulating]
Up: [computational_problem] on [tree]
-Aliases: TreeEval
+Aliases: TreeEval, tree evaluation
See also: [formula_value_problem]
diff --git a/vector_addition_system_pushdown b/vector_addition_system_pushdown
@@ -4,8 +4,11 @@
Unclear if [reachability] is [decidable]
- cf [ganardi2022reachability]
+- cf [biziere2025reachability] for one-dimensional
- claimed decidable in [guttenberg2026pvass]
Also with counters and with resets [schmitz2019coverability] (but for [coverability])
Up: [vector_addition_system], [pushdown_automaton]
+
+Aliases: pushdown VAS, pushdown VASS
