commit 87f86f82a9d8f1a78cf937fdf47a0be64086d446
parent a0505616ae96f2e4293bf8561b8a99881213d217
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 12 Jun 2025 14:52:53 +0200
commit with codex
Diffstat:
15 files changed, 106 insertions(+), 8 deletions(-)
diff --git a/approximate_pattern_matching b/approximate_pattern_matching
@@ -0,0 +1,15 @@
+# Approximate pattern matching
+
+- find all occurrences of a pattern P in text T up to k modifications ([edit_distance])
+- only report the end of matches to avoid quadratic output
+
+variant: [approximate_pattern_matching_streaming]
+
+[academic_papers]:
+
+- [hazay2007approximate]
+- [bathie2024longest]
+
+Up: [pattern_matching], [approximation]
+
+Aliases: pattern matching approximate
diff --git a/bathie2021property b/bathie2021property
@@ -0,0 +1,15 @@
+# bathie2021property
+
+by [gabriel] and [tatiana_starikovskaya]
+
+- Shows that there is a "hard" [regular_language] for which [property_testing_formal_language] requires Omega(log(1/ε)/ε)
+- There are "easy" [regular_languages] needing Theta(1/ε) queries
+ - e.g., a^*
+- There are "trivial" [regular_languages] where 0 queries are needed for large enough n
+ - any sufficiently long [word] cannot be [epsilon_far] from the [formal_language]
+
+Uses the notion of [blocking_factor]: they sample random [factors] and check if they are [blocking_factors]
+
+Follow-up: [bathie2025trichotomy]
+
+Up: [academic_paper] on [property_testing_formal_language]
diff --git a/bathie2024longest b/bathie2024longest
@@ -0,0 +1,7 @@
+# bathie2024longest
+
+- [approximate_pattern_matching]
+- [LCEW]
+- gives an [algorithm] for [sparse_BMM]
+
+Up: [academic_paper], [gabriel]
diff --git a/blocking_factor b/blocking_factor
@@ -2,7 +2,7 @@
A blocking factor of a [language] is a [word] which never occurs as a [factor] of a [word] of the language
-- [blocking_factor_minimal]
+- [minimal_blocking_factor]
- [blocking_sequence]
- [blocking_sequence_minimal]
@@ -11,7 +11,7 @@ A blocking factor of a [language] is a [word] which never occurs as a [factor] o
even for [strongly_connected] [NFA], it's [PSPACE_complete]
- reduction from [NFA_universality]
-See also: [links_seminar_gabriel], [property_testing]
+See also: [links_seminar_gabriel], [property_testing], [Mortal_word]
Aliases: blocking factors
diff --git a/blocking_factor_minimal b/blocking_factor_minimal
@@ -0,0 +1,11 @@
+# Blocking factor minimal
+
+A [blocking_factor] where no proper [factor] is a [blocking_factor]
+
+The set of [minimal_blocking_factors] of a [regular_language] is a [regular_language] ([bathie2025trichotomy], Lemma 3.15)
+
+Up: [blocking_factor]
+
+Aliases: minimal blocking factor, minimal blocking factors
+
+See also: [minimal_language]
diff --git a/boolean_matrix_multiplication b/boolean_matrix_multiplication
@@ -9,4 +9,4 @@ Variants:
Up: [matrix_multiplication] for [boolean_semiring], [fine_grained_complexity_problems]
-Aliases: matrix multiplication Boolean
+Aliases: matrix multiplication Boolean, BMM
diff --git a/longest_common_extension b/longest_common_extension
@@ -4,6 +4,10 @@ Uses [suffix_array]
Related open problem: [mirror_lce]
+Generalization: [longest_common_extension_wildcards]
+
Up: [stringology]
See also: [longest_common_subsequence]
+
+Aliases: LCE
diff --git a/longest_common_extension_wildcards b/longest_common_extension_wildcards
@@ -0,0 +1,17 @@
+# Longest common extension wildcards
+
+[longest_common_extension] with [wildcards]
+
+result by [crochemore]: [crochemore2015note]
+- time O(nG) to build, with G the number of groups of wildcards
+- constant time querying
+
+[bathie2024longest]
+- allows tradeoffs
+- lower bounds from [BMM]
+
+Can be used for [approximate_pattern_matching]
+
+Up: [longest_common_extension]
+
+Aliases: LCEW
diff --git a/metadichotomy b/metadichotomy
@@ -4,4 +4,4 @@ The [computational_problem] of deciding which case of a [dichotomy] result appli
Up: [dichotomy]
-Aliases: meta_dichotomy
+Aliases: meta_dichotomy, metadichotomy criterion, metadichotomy criteria
diff --git a/palindromic_length b/palindromic_length
@@ -0,0 +1,7 @@
+# Palindromic length
+
+[computational_problem] of deciding, given a [word] w and an [integer] k, whether w is the concatenation of k [palindromes]
+
+[Academic_paper]: [bathie2025small]
+
+Up: [computational_problem]
diff --git a/property_testing_formal_language b/property_testing_formal_language
@@ -2,8 +2,10 @@
- [alon2001regular] on [regular_languages]
- [Otilde](1/ε) bits are enough to know [with_high_probability] whether you need to change at least εn positions to belong to the target [regular_language]
+ - more precisely O(log^3(1/ε) / ε)
- uses [hamming_distance]
-- [ndione2013approximate] for [edit_distance]:
+- [ndione2013approximate] for [levenshtein_distance]:
+ - uses the [levenshtein_distance], which is weaker
- but the result is wrong according to [bathie2021property]
- [bathie2021property] on [regular_languages]
- uses the [levenshtein_distance], which is weaker
diff --git a/sparse_bmm_hypothesis b/sparse_bmm_hypothesis
@@ -0,0 +1,6 @@
+# Sparse bmm hypothesis
+
+[boolean_matrix_multiplication] cannot be
+performed in [linear_time] in the number of 1 entries
+
+Up: [complexity_hypothesis], [sparse_boolean_matrix_multiplication]
diff --git a/sparse_boolean_matrix_multiplication b/sparse_boolean_matrix_multiplication
@@ -1,10 +1,13 @@
# Sparse BMM
-[computational_hypothesis] : [boolean_matrix_multiplication] cannot be
-performed in [linear_time] in the number of 1 entries
+The [computational_problem] of [BMM] with [sparse_matrices]
+
+[computational_hypothesis]: [sparse_bmm_hypothesis]
Also: [fully_sparse_boolean_matrix_multiplication]
Up: [fine_grained_complexity]
See also: [boolean_matrix_multiplication], [sparse]
+
+Aliases: sparse BMM
diff --git a/visibly_pushdown_automaton b/visibly_pushdown_automaton
@@ -4,6 +4,6 @@
Up: [pushdown_automaton]
-See also: [tree_automaton]
+See also: [tree_automaton], [visibly_pushdown_language]
Aliases: VPA, VPAs, visibly pushdown automata, input driven automaton, input driven automata, input-driven automaton, input-driven automata
diff --git a/visibly_pushdown_language b/visibly_pushdown_language
@@ -0,0 +1,11 @@
+# Visibly pushdown language
+
+A [formal_language] recognized by a [visibly_pushdown_automaton]
+
+This is a subclass of [context_free_languages]
+
+Up: [formal_language]
+
+See also: [tree_language]
+
+Aliases: VPL, VPLs, visibly pushdown languages
