commit bba59584e8f4c2a2c0374b8563d4f1a9f71f1ac4
parent 33615eaebb57920a93693a277e6b647d5efb2638
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 31 Dec 2025 16:34:22 +0100
commit with codex
Diffstat:
15 files changed, 49 insertions(+), 9 deletions(-)
diff --git a/algorithm_randomized b/algorithm_randomized
@@ -16,4 +16,4 @@ Up: [algorithms]
See also: [fpras], [rp], [complexity_random], [randomness], [derandomization], [randomized_reduction]
-Aliases: randomized
+Aliases: randomized, randomized algorithm, randomized algorithms
diff --git a/approximate_pattern_matching b/approximate_pattern_matching
@@ -1,10 +1,16 @@
# Approximate pattern matching
-- find all occurrences of a pattern P in text T up to k modifications ([edit_distance])
+- find all occurrences of a pattern P in text T up to k modifications ([string_distance])
- only report the end of matches to avoid quadratic output
+can be for [hamming_distance] or for [edit_distance] (cf [navarro2001guided])
+
variant: [approximate_pattern_matching_streaming]
+special cases when the [string_distance] is not too big (bounded by k):
+- [k_mismatch_pattern_matching] for [hamming_distance]
+- [k_edit_pattern_matching] for [edit_distance]
+
[academic_papers]:
- [hazay2007approximate]
diff --git a/arithmetic b/arithmetic
@@ -9,6 +9,7 @@
- [modulo]
- [GCD]
- [coprime]
+- [chinese_remainder_theorem]
Up: [mathematics]
diff --git a/datalog_negation b/datalog_negation
@@ -7,6 +7,10 @@ Simple solution: [negation_stratified], i.e., adding [negation] only to [datalog
Recent work on this: [shaikhha2024optimizing]
+[datalog_negation_provenance]
+
See also: [fixpoint]
-Up: [datalog], [negation]
+Up: [datalog], [negation], [datalog_extensions]
+
+Aliases: datalog with negation
diff --git a/datalog_negation_provenance b/datalog_negation_provenance
@@ -0,0 +1,7 @@
+# Datalog negation provenance
+
+[bogaerts2025why]
+
+Up: [datalog_negation], [datalog_provenance]
+
+Aliases: datalog provenance negation
diff --git a/enumeration_spanner b/enumeration_spanner
@@ -5,4 +5,4 @@
Up: [enumeration] for [spanner]
-See also: [enumeration_strings]
+See also: [enumeration_strings], [regular_expression_pattern_matching_problem]
diff --git a/k_mismatch_pattern_matching b/k_mismatch_pattern_matching
@@ -0,0 +1,7 @@
+# K mismatch pattern matching
+
+[gawrychowski2018towards]
+
+Up: [approximate_pattern_matching]
+
+See also: [k_edit_pattern_matching]
diff --git a/language_distance_problem b/language_distance_problem
@@ -0,0 +1,5 @@
+# Language distance problem
+
+Given a [formal_language] and a [word], compute the [string_distance] of the [word] to the [formal_language]
+
+Up: [regular_language_membership]
diff --git a/pattern_matching b/pattern_matching
@@ -32,6 +32,7 @@
- [pattern_matching_dontcare] when allowing [dontcares] (one single symbol can be anything)
- [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
## Implementations
diff --git a/pattern_matching_practice b/pattern_matching_practice
@@ -1,6 +1,6 @@
# Pattern matching practice
-- https://smart-tool.github.io/smart/
+- [smart_tool]: https://smart-tool.github.io/smart/
- [strstr]
- uses [two_way_string_matching_algorithm]?
diff --git a/pattern_matching_streaming b/pattern_matching_streaming
@@ -1,5 +1,7 @@
# Pattern matching streaming
-you get the pattern character by character and must build a [sketching] of the pattern, and then you get the text character by character and must match
+setting 1: you get the pattern character by character and must build a [sketching] of the pattern, and then you get the text character by character and must match
+setting 2: you know the pattern and get the text character by character and must limit [space_complexity] and [time_complexity]
+ - cf [pattern_matching_streaming_algorithms]
-Up: [approximate_pattern_matching_streaming]
+- [approximate_pattern_matching_streaming]
diff --git a/provenance_datalog b/provenance_datalog
@@ -13,4 +13,9 @@ Subcases:
- [calautti2023complexity]: [provenance_membership_testing]
- [convergence] for [datalog]: [abokhamis2021convergence]
+For [datalog_extensions]:
+- [datalog_negation_provenance]
+
+- [bogaerts2025why] pour [datalog_with_negation]
+
Up: [provenance], [datalog]
diff --git a/regular_language_membership b/regular_language_membership
@@ -6,3 +6,5 @@
- [regular_expression_matching]
Up: [membership_problem] for [regular_language]
+
+See also: [language_distance_problem]
diff --git a/square_word b/square_word
@@ -6,4 +6,4 @@ Up: [word]
See also: [twin], [square_free_word], [square_language], [non_square_word], [repetitive_string], [Shuffle_square], [cube_word]
-Aliases: word square, word squares
+Aliases: word square, word squares, string square, string squares
diff --git a/strahler_number b/strahler_number
@@ -11,4 +11,4 @@ Related to [pathwidth] by a factor of 2
Up: [parameter] on [tree]
-See also: [cantor_bendixson_rank]
+See also: [cantor_bendixson_rank], [ganardi2025complexity]
