wiki_research

commit bb747ae4a92411679392c8372d21dd3e3e8089ce
parent d7878eb709d0c8b0bcd603370b287f73b80164ac
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Thu, 25 Sep 2025 15:01:13 +0200

commit with codex

Diffstat:
context_free_grammar_equivalence_problem
 | 
2
+-
context_free_grammar_linear
 | 
5
++++-
linear_cfg_equivalence
 | 
7
+++++++
linear_cfg_universality
 | 
7
+++++++
universality_context_free_grammar
 | 
3
++-

5 files changed, 21 insertions(+), 3 deletions(-)
diff --git a/context_free_grammar_equivalence_problem b/context_free_grammar_equivalence_problem
@@ -2,7 +2,7 @@
 
 The *context free grammar equivalence problem* is the [decision_problem] of testing, given two [CFGs], whether they are [CFG_equivalent]
 
-It is [undecidable] on [CFGs], by reduction from [CFG_universality]
+It is [undecidable] on [CFGs], by reduction from [CFG_universality]. It is already [undecidable] on [linear_CFGs], cf [linear_CFG_equivalence]
 
 - for [uCFGs] (or with multiplicity of [parse_trees]): [context_free_grammar_unambiguous_equivalence_problem]
 
diff --git a/context_free_grammar_linear b/context_free_grammar_linear
@@ -2,7 +2,10 @@
 
 https://en.wikipedia.org/wiki/Linear_grammar
 
-Testing [language_emptiness] of [intersection] is already [undecidable] by reduction from [post_correspondence_problem]
+[Computational_problems]:
+- [linear_CFG_universality]
+- [linear_CFG_equivalence]
+- Testing [language_emptiness] of [intersection] is already [undecidable] by reduction from [post_correspondence_problem]
 
 Up: [context_free_grammar]
 
diff --git a/linear_cfg_equivalence b/linear_cfg_equivalence
@@ -0,0 +1,7 @@
+# Linear CFG equivalence
+
+The [context_free_grammar_equivalence_problem] on [linear_CFGs]
+
+It is [undecidable] by [baker1974reversal], cf [yehudai1980decidability]
+
+Up: [context_free_grammar_equivalence_problem], [linear_CFG]
diff --git a/linear_cfg_universality b/linear_cfg_universality
@@ -0,0 +1,7 @@
+# Linear CFG universality
+
+The [universality_problem_CFG] for [linear_CFGs]
+
+It is [undecidable] by [baker1974reversal], see [hoogeboom2015undecidable]
+
+Up: [universality_problem_CFG], [context_free_grammar_linear]
diff --git a/universality_context_free_grammar b/universality_context_free_grammar
@@ -3,9 +3,10 @@
 [universality_problem] for [CFGs]: it is [undecidable]
 
 - for [uCFGs]: [universality_context_free_grammar_unambiguous]
+- for [linear_CFGs]: [linear_CFG_universality]
 
 Up: [universality_problem]
 
 See also: [universality_automata]
 
-Aliases: CFG universality, context free grammar universality, universality CFG
+Aliases: CFG universality, context free grammar universality, universality CFG, universality problem CFG, universality problem CFGs