wiki_research

commit 1a5eb166d802642d56f43e36e706b39254789005
parent 21e1e92a496675a97e44a71fba3aa47766bcb2cf
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Sat, 20 Sep 2025 21:12:24 +0200

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

Diffstat:
2_ambiguous_cfg
 | 
3
+++
context_free_grammar
 | 
3
+++
context_free_grammar_ambiguity_problem
 | 
9
+++++++++
context_free_grammar_equivalence
 | 
2
++
context_free_grammar_inclusion
 | 
7
+++++++
context_free_grammar_unambiguous
 | 
1
+
language_inclusion
 | 
1
+

7 files changed, 26 insertions(+), 0 deletions(-)
diff --git a/2_ambiguous_cfg b/2_ambiguous_cfg
@@ -2,6 +2,9 @@
 
 A *2-ambiguous CFG* is an [ambiguous_CFG] where every [word] has at most two [parse_trees]
 
+- [universality_2_ambiguous_CFG]
+- [equivalence_2_ambiguous_CFG]
+
 Up: [degree_of_ambiguity_cfg]
 
 Aliases: 2 ambiguous CFGs, 2ambiguous CFG, 2ambiguous CFGs
diff --git a/context_free_grammar b/context_free_grammar
@@ -35,9 +35,11 @@
 ## Problems
 
 - [context_free_grammar_equivalence]
+- [context_free_grammar_inclusion]
 - [context_free_grammar_universality]
 - [smallest_grammar_problem]
 - [context_free_grammar_membership]
+- [context_free_grammar_ambiguity_problem]
 
 ## Fields
 
@@ -46,6 +48,7 @@
 ## Extensions
 
 - [probabilistic_grammar]
+- [conjunctive_grammar]
 - [multiple_context_free_grammar]
 
 ## Results
diff --git a/context_free_grammar_ambiguity_problem b/context_free_grammar_ambiguity_problem
@@ -0,0 +1,9 @@
+# Context free grammar ambiguity problem
+
+The [computational_problem] of [deciding] if a [CFG] is [uCFG]
+
+Already [undecidable] for very restricted [linear_CFGs] by reduction from [PCP]
+
+Up: [ambiguity_problem], [context_free_grammar]
+
+See also: [context_free_language_inherent_ambiguity_problem]
diff --git a/context_free_grammar_equivalence b/context_free_grammar_equivalence
@@ -7,3 +7,5 @@ Two [CFGs] are *equivalent* if they recognize the same [formal_language]
 Up: [context_free_grammar], [language_equivalence]
 
 Aliases: CFG equivalence, CFG equivalent, equivalent CFG, grammar equivalent
+
+See also: [context_free_grammar_inclusion]
diff --git a/context_free_grammar_inclusion b/context_free_grammar_inclusion
@@ -0,0 +1,7 @@
+# Context free grammar inclusion
+
+It is [undecidable], already for [uCFLs], and already for [linear_uCFLs], see [asveld2000note]
+
+Up: [inclusion_problem], [context_free_grammar]
+
+Aliases: CFG inclusion
diff --git a/context_free_grammar_unambiguous b/context_free_grammar_unambiguous
@@ -10,6 +10,7 @@ There are some [CFLs] admitting no uCFG (namely, those that are not [uCFLs]), an
 [Computational_problems]:
 
 - [unambiguous_cfg_equivalence_problem]
+- [unambiguous_cfg_inclusion_problem]
 - [unambiguous_cfg_universality]
 
 Up: [unambiguity], [context_free_grammar]
diff --git a/language_inclusion b/language_inclusion
@@ -4,5 +4,6 @@
 - [language_inclusion_bounded]
 - [DPDA_language_inclusion]
 - [automaton_inclusion]
+- [CFG_language_inclusion]
 
 Up: [formal_language_computational_problems], [set_inclusion]