wiki_research

commit ed7774f192c1c1de1dd52644b97f3411cf7f7f31
parent 82915d58c6276b6261daea52abe94550cc5f7978
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Mon, 17 Mar 2025 13:54:39 +0100

Merge branch 'master' of a3nm.net:git/wiki_research

Diffstat:
approximation_class
 | 
4
++--
bounded_problem
 | 
11
+++++++++++
formal_language_computational_problems
 | 
1
+
language_inclusion
 | 
1
+
language_inclusion_bounded
 | 
9
+++++++++
locally_threshold_testable_language
 | 
16
++++++++++++++++

6 files changed, 40 insertions(+), 2 deletions(-)
diff --git a/approximation_class b/approximation_class
@@ -1,9 +1,9 @@
 # Approximation classes
 
 - [FPRAS]: for all epsilon you have an [algorithm_randomized] running in polynomial time in 1/e and in the input, with a probability delta of failure
-  - variant QPRAS [qpras] with "quasi-polynomial time" [quasipolynomial]
+  - variant [QPRAS] with [quasi-polynomial] time
 - [PRAS]: same but not polynomial in 1/e
-- without R, a deterministic algorithm (PRAS vs [PTAS], FPRAS vs [FPTAS])
+- without R, a deterministic algorithm ([PRAS] vs [PTAS], [FPRAS] vs [FPTAS])
 - [APX]: there is an [approximation_algorithm] for a certain fixed epsilon
 
 Up: [complexity_class] of [approximation]
diff --git a/bounded_problem b/bounded_problem
@@ -0,0 +1,11 @@
+# Bounded problem
+
+studied in [axelsson2008analyzing]
+
+- [language_inclusion_bounded]
+- [language_equivalence_bounded]
+- [language_intersection_bounded]
+- [language_universality_bounded]
+- [CFG_ambiguity_bounded]
+
+Up: [formal_language_computational_problem]
diff --git a/formal_language_computational_problems b/formal_language_computational_problems
@@ -3,6 +3,7 @@
 - [membership_problem]
 - [language_inclusion]
 - [language_equivalence]
+- [bounded_problem]
 
 Up: [formal_language]
 
diff --git a/language_inclusion b/language_inclusion
@@ -1,6 +1,7 @@
 # Language inclusion
 
 - [pattern_language_inclusion]
+- [language_inclusion_bounded]
 
 Up: [formal_language_computational_problems], [inclusion]
 
diff --git a/language_inclusion_bounded b/language_inclusion_bounded
@@ -0,0 +1,9 @@
+# Language inclusion bounded
+
+Given two [formal_languages] L_1 and L_2, and a length k, is it true that L_1 cap Sigma^{\leq k} is included in L2 cap Sigma^{\leq k}?
+
+studied in [axelsson2008analyzing]
+
+Up: [language_inclusion], [bounded_problem]
+
+Aliases: bounded language inclusion
diff --git a/locally_threshold_testable_language b/locally_threshold_testable_language
@@ -0,0 +1,16 @@
+# Locally_threshold_testable_language
+
+Discussed in [bojanczyk2007new]
+
+A [formal_language] is *locally threshold testable* if it is a [Boolean_combination] of [formal_languages] of the form:
+- words having a given [word] w as a [prefix]
+- words having a given [word] w as a [suffix]
+- words having a given [word] w as a [factor] at least n times
+
+Generalizes [locally_testable_languages]
+
+Up: [locally_testable_language]
+
+See also: [local_language]
+
+Aliases: LTT language, LTT