wiki_research

commit 0806b988121a708c5d7b0342223bc81026943ca1
parent 65541bcfc4fc4f1b3d0d29feafe6ac6f99270005
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue, 16 Sep 2025 14:46:24 +0200

commit with codex

Diffstat:
context_free_language
 | 
11
+++++++++++
context_free_language_linear
 | 
11
+++++++++++
context_free_language_unambiguous
 | 
3
+++
intersection
 | 
2
+-
palindrome
 | 
2
+-
palindrome_language
 | 
7
+++++++
union
 | 
2
+-

7 files changed, 35 insertions(+), 3 deletions(-)
diff --git a/context_free_language b/context_free_language
@@ -13,6 +13,17 @@ Subclass:
 - [context_free_language_linear]
 - [context_free_language_deterministic_linear]
 
+Variants:
+
+- CFL [cap] [coCFL]:
+  - contains [DCFL]
+  - also contains [palindrome_language]
+    - https://cstheory.stackexchange.com/a/4264
+  - testing membership is [undecidable]
+    - https://cstheory.stackexchange.com/a/20727
+- CFL [cup] [coCFL]:
+  - https://cstheory.stackexchange.com/q/9098
+
 Up: [language], [context_free_grammar]
 
 Aliases: context-free languages, context free languages, context-free language, CFL, CFLs
diff --git a/context_free_language_linear b/context_free_language_linear
@@ -0,0 +1,11 @@
+# Context free language linear
+
+A *linear context-free language* is a [CFL] that is recognized by a [linear_CFG]
+
+Special cases:
+- [unambiguous_linear_CFL]
+- [deterministic_linear_CFL]
+
+Up: [context_free_language]
+
+Aliases: linear context-free language, linear context-free languages
diff --git a/context_free_language_unambiguous b/context_free_language_unambiguous
@@ -2,6 +2,9 @@
 
 An *unambiguous context free language* is a [CFL] that can be accepted by a [uCFG], i.e., it is a [CFL] which is not [inherently_ambiguous].
 
+Special cases:
+- [linear_unambiguous_CFLs]
+
 Up: [context_free_language]
 
 Aliases: uCFL, uCFLs, unambiguous CFL, unambiguous CFLs, unabiguous context free language, unambgiuous context free languages
diff --git a/intersection b/intersection
@@ -7,4 +7,4 @@
 
 Up: [boolean_operator]
 
-Aliases: intersections
+Aliases: intersections, cap
diff --git a/palindrome b/palindrome
@@ -4,6 +4,6 @@ A [word] which is equal to its [mirror]
 
 Up: [word]
 
-See also: [manachers_algorithm], [context_free_language]
+See also: [manachers_algorithm], [context_free_language], [palindrome_language]
 
 Aliases: palindromes
diff --git a/palindrome_language b/palindrome_language
@@ -0,0 +1,7 @@
+# Palindrome language
+
+The [formal_language] of the [words] that are [palindromes]
+
+Up: [formal_language], [palindrome]
+
+See also: [square_language]
diff --git a/union b/union
@@ -8,4 +8,4 @@ Up: [set_theory], [boolean_operator]
 
 See also: [disjunction]
 
-Aliases: unions
+Aliases: unions, cup