commit 3ac2fd2e350cfa5608f2396c8a2c20d4de028419
parent ac9936a9d76b04a709c5ecbfc5b9dc4243649e36
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 30 May 2025 18:00:00 +0200
commit with codex
Diffstat:
4 files changed, 37 insertions(+), 0 deletions(-)
diff --git a/approximate_membership b/approximate_membership
@@ -0,0 +1,9 @@
+# Approximate membership
+
+Problem of [approximation] of [formal_language_membership]
+
+Common model in which to do it: [property_testing_formal_language]
+
+See also: [dynamic_membership]
+
+Up: [regular_language_membership]
diff --git a/membership_problem b/membership_problem
@@ -3,8 +3,11 @@
given [formal_language] L description and [word] w, test if w belongs to L
- [regular_language_membership]
+- [pattern_language_membership]
- [context_free_language_membership]
- [radoszewski2021hardness] for hardness under [3SUM_conjecture] of testing membership of a string to some [formal_languages]
Up: [formal_language_computational_problem]
+
+Aliases: formal language membership problem, formal language membership
diff --git a/property_testing b/property_testing
@@ -0,0 +1,8 @@
+# Property testing
+
+- [property_testing_formal_language]
+- [adler2018property]
+
+Up: [computational_problem]
+
+See also: [model_checking], [Approximate_membership]
diff --git a/property_testing_formal_language b/property_testing_formal_language
@@ -0,0 +1,17 @@
+# Property testing formal language
+
+- [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]
+ - uses [hamming_distance]
+- [ndione2013approximate] for [edit_distance]:
+ - but the result is wrong according to [bathie2021property]
+- [bathie2021property] on [regular_languages]
+ - uses the [levenshtein_distance], which is weaker
+- [bathie2025trichotomy] on [regular_languages]
+ - uses the [hamming_distance]
+ - gives a precise description of the complexity as a function of ε
+- [francois2015streaming] on [visibly_pushdown_languages]
+- [fischer2010approximate] for [edit_distance_with_moves]
+ - called "approximate satisfiability"
+
+Up: [property_testing], [formal_language]
