commit 053fe16a2081b8551dae1a71a2dad479cc2747b5
parent 730f3ac0be2f4e703553a94f70823d0f4e65cd4b
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 16 Sep 2025 11:27:07 +0200
commit with codex
Diffstat:
9 files changed, 78 insertions(+), 2 deletions(-)
diff --git a/composite_word b/composite_word
@@ -0,0 +1,11 @@
+# Composite word
+
+A [word] which is not a [primitive_word]
+
+Special cases:
+
+- [square_word]
+
+Up: [primitive_word]
+
+See also: [composite_word_language]
diff --git a/non_square_word b/non_square_word
@@ -0,0 +1,9 @@
+# Non square word
+
+A [word] which is not a [square_word]
+
+Up: [square_word]
+
+See also: [non_square_word_language], [Primitive_word]
+
+Aliases: non square words
diff --git a/non_square_word_language b/non_square_word_language
@@ -0,0 +1,9 @@
+# Non square word language
+
+The [formal_language] of [non_square_words]
+
+It is a [CFL], as can be seen on a [pushdown_automaton]
+
+The same argument shows that the [formal_language] of languages that cannot be written as u^p is a [CFL] for any fixed p, but the same reasoning does not apply to the [primitive_words_language]
+
+Up: [formal_language] of [non_square_words]
diff --git a/primitive_word b/primitive_word
@@ -6,8 +6,11 @@ A [word] which is not a [power_mathematics] of another [word]
The [formal_language] of such words: [primitive_word_language]
+Special cases:
+- [non_square_word]
+
Up: [word]
-See also: [prime_number], [prime_number_decomposition], [primitive_word_conjecture]
+See also: [prime_number], [prime_number_decomposition], [primitive_word_conjecture], [composite_word]
Aliases: primitive words
diff --git a/primitive_word_language b/primitive_word_language
@@ -2,6 +2,16 @@
The [formal_language] of all [primitive_words]
-It is an [open_problem] whether it is a [CFL], but it is known that it is not a [uCFL] by [petersen1996language]
+It is an [open_problem] whether it is a [CFL], but it is known that it is not a [uCFL] by [petersen1996language] and not a [linear_CFL] by [horvath1995strong]
+
+The [language_complement] (the [formal_language] of all [composite_words]) is not a [CFL]: https://cstheory.stackexchange.com/questions/55739/context-freeness-of-the-language-of-composite-non-primitive-words/55740#55740
+
+Discussed in [lischke2011primitive]
+
+[Book] on the topic: [domosi2014context]
Up: [formal_language], [primitive_word]
+
+See also: [square_language]
+
+Aliases: primitive words language
diff --git a/pumping_lemma b/pumping_lemma
@@ -0,0 +1,7 @@
+# Pumping lemma
+
+- [pumping_lemma_regular_languages]
+- [pumping_lemma_CFL]
+ - [Ogden's_lemma]
+
+Up: [formal_language_theory]
diff --git a/pumping_lemma_cfl b/pumping_lemma_cfl
@@ -0,0 +1,9 @@
+# Pumping lemma for CFLs
+
+https://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages
+
+Also known as the "Bar-Hillel, Perles, Shamir" [theorem]
+
+Up: [pumping_lemma] for [CFLs]
+
+Aliases: pumping lemma for CFLs, CFL pumping lemma
diff --git a/square_language b/square_language
@@ -0,0 +1,9 @@
+# Square language
+
+The [formal_language] of all [words] that are [word_squares]
+
+It is not a [CFL], by immediate application of the [CFL_pumping_lemma]
+
+Up: [square_word]
+
+See also: [square_free_word_language], [square_factor_language]
diff --git a/square_word b/square_word
@@ -0,0 +1,9 @@
+# Square word
+
+A [word] of the form uu
+
+Up: [word]
+
+See also: [twin], [square_free_word], [square_language], [non_square_word]
+
+Aliases: word square, word squares
