commit 661e6a4b8be443936679adf2763bd80cb156fcf4
parent 0fc6762b6c647c7c9ba0931cb53026006d293953
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 12 Jan 2025 00:56:31 +0100
commit with codex
Diffstat:
18 files changed, 93 insertions(+), 6 deletions(-)
diff --git a/boolean_function b/boolean_function
@@ -10,7 +10,8 @@ Generalizations:
Notions:
- [boolean_operator]
-- [prime_implicant]
+- [implicant]
+ - [prime_implicant]
- [subfunction]
- [boolean_valuation]
- [satisfying_valuation]
diff --git a/boolean_operator b/boolean_operator
@@ -5,6 +5,7 @@
- [xor]
- [negation] / [complementation]
- [setminus]
+- [logical_implication]
Up: [boolean_function]
diff --git a/boyer_moore b/boyer_moore
@@ -0,0 +1,7 @@
+# Boyer-Moore
+
+https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm
+
+Up: [pattern_matching_algorithm]
+
+Aliases: Boyer Moore algorithm, Boyer-Moore algorithm
diff --git a/edit_distance_oracle b/edit_distance_oracle
@@ -1,6 +1,6 @@
# Edit distance oracle
-given two [string]s, index them so that given two [subword] you can quickly compute the edit distance:
+given two [strings], index them so that given two [subwords] you can quickly compute the [edit_distance]:
- [charalampopoulos2021almost]
diff --git a/game_on_graphs b/game_on_graphs
@@ -0,0 +1,8 @@
+# Game on graphs
+
+- [network_creation_game]
+- [pursuit_evasion]
+
+Up: [games], [graph]
+
+Aliases: games on graphs, games on graph
diff --git a/graph b/graph
@@ -52,6 +52,7 @@ See [graph_problem]
- [graph_theory]
- [pursuit_evasion]
- [extremal_graph_theory]
+ - [games_on_graphs]
## Constructions
diff --git a/graph_theory b/graph_theory
@@ -2,7 +2,8 @@
- [friendship_theorem]
- [handshaking_lemma]
-- [pursuit_evasion]
- [extremal_graph_theory]
+- [games_on_graphs]
+ - [pursuit_evasion]
Up: [theoretical_computer_science] on [graph]
diff --git a/hamming_distance b/hamming_distance
@@ -0,0 +1,9 @@
+# Hamming distance
+
+https://en.wikipedia.org/wiki/Hamming_distance
+
+- [hamming_distance_sketching]
+
+See also: [hamming_weight]
+
+Up: [string_distance]
diff --git a/hyperedge b/hyperedge
@@ -0,0 +1,7 @@
+# Hyperedge
+
+A set of [vertices] in a [hypergraph]
+
+Up: [hypergraph], [edge]
+
+Aliases: hyperedges
diff --git a/implicant b/implicant
@@ -0,0 +1,9 @@
+# Implicant
+
+https://en.wikipedia.org/wiki/Implicant
+
+For a [Boolean_function], an implicant is a [term] which [implies] the function, i.e., suffices to make it true
+
+- [prime_implicant]
+
+Up: [boolean_function]
diff --git a/logic b/logic
@@ -62,6 +62,7 @@
- [monadic]
- [logic_formula]
- [quantifier]
+- [logical_implication]
Up: [mathematics], [theoretical_computer_science]
diff --git a/marx2020four b/marx2020four
@@ -0,0 +1,9 @@
+# Marx2020four
+
+- [bidimensionality]
+- [maximum_independent_set], beating the naive exponential algorithm
+- [permutation_pattern]
+
+similar paper: [pilipczuk2020surprising]
+
+Up: [academic_paper], [treewidth_practical]
diff --git a/pattern_language_inclusion b/pattern_language_inclusion
@@ -0,0 +1,7 @@
+# Pattern language inclusion
+
+[language_inclusion] for [pattern_languages]: given two [patterns_with_variables], decide if one is included in the other
+
+- [nowotka2024equivalence]: it is [undecidable]
+
+Up: [pattern_language_computational_problems], [language_inclusion]
diff --git a/pseudo_polynomial_time b/pseudo_polynomial_time
@@ -0,0 +1,11 @@
+# Pseudo polynomial time
+
+https://en.wikipedia.org/wiki/Pseudo-polynomial_time
+
+There is an [algorithm] running in [PTIME] in the number of input integers and in the value of the greatest integer
+
+So it is not really a [PTIME] algorithm in the size of the input integers
+
+See also: [ptime], [np_complete], [strongly_np_complete], [quasipolynomial]
+
+Up: [computational_complexity]
diff --git a/pursuit_evasion b/pursuit_evasion
@@ -7,4 +7,4 @@ notion:
- [monotone_strategy], cf for instance [dissaux2023recontamination]
- [capture_time], cf for instance [benameur2024cops]
-Up: [graph]
+Up: [games_on_graph]
diff --git a/signed_hyperorderwidth b/signed_hyperorderwidth
@@ -0,0 +1,5 @@
+# Signed hyperorderwidth
+
+Given a [hypergraph_signed], consider all possible subsets S of the negative [hyperedges], and consider the [hyperorderwidth] of the positive [hyperedges] plus S
+
+Up: [width_measure], [capelli2023direct]
diff --git a/string_distance b/string_distance
@@ -0,0 +1,10 @@
+# String distance
+
+- [edit_distance]
+ - [levenshtein_distance]
+- [hamming_distance]
+- [dynamic_time_warping]
+
+Up: [distance] on [string]
+
+See also: [edit_distance]
diff --git a/subword b/subword
@@ -1,8 +1,8 @@
# Subword
-u subword of v means v = xuy
+u subword of v means v = xuy; also called a "factor" or an "infix"
-not contiguous, unlike [subsequence]
+must be contiguous, unlike [subsequence]
- [subword_automaton]
