wiki_research

commit 79f9218af05c2d525febb0283b65c217784d5b8c
parent cc65397d2aaf39592bef461effb5a7a9119209ca
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Thu,  6 Mar 2025 20:58:43 +0100

commit with codex

Diffstat:
bounded_problem
 | 
11
+++++++++++
formal_language_computational_problems
 | 
1
+
language_inclusion
 | 
1
+
language_inclusion_bounded
 | 
9
+++++++++

4 files changed, 22 insertions(+), 0 deletions(-)
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