commit 65541bcfc4fc4f1b3d0d29feafe6ac6f99270005
parent 053fe16a2081b8551dae1a71a2dad479cc2747b5
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 16 Sep 2025 12:00:48 +0200
commit with codex
Diffstat:
10 files changed, 60 insertions(+), 5 deletions(-)
diff --git a/composite_word b/composite_word
@@ -9,3 +9,5 @@ Special cases:
Up: [primitive_word]
See also: [composite_word_language]
+
+Aliases: composite words
diff --git a/composite_word_language b/composite_word_language
@@ -0,0 +1,9 @@
+# Composite word language
+
+The [formal_language] of all [composite_words]
+
+It is not a [CFL]:
+- https://cstheory.stackexchange.com/questions/55739/context-freeness-of-the-language-of-composite-non-primitive-words/55740#55740
+- given in [domosi2015context]
+
+Up: [formal_language] of [composite_words]
diff --git a/context_free b/context_free
@@ -0,0 +1,6 @@
+# Context free
+
+- [context_free_grammar]
+- [context_free_language]
+
+Up: [Formal_language_theory]
diff --git a/context_free_grammar b/context_free_grammar
@@ -53,6 +53,6 @@
See also: [regular_language], [chomsky_hierarchy], [context_free_language], [inherently_ambiguous], [graph_grammar], [semilinear_set], [language_power_series], [Hyperedge_replacement_grammar]
-Up: [formal_language_theory], [formal_grammar]
+Up: [formal_language_theory], [formal_grammar], [context_free]
Aliases: CFG, CFGs, context free grammars, context-free grammars
diff --git a/primitive_word_language b/primitive_word_language
@@ -4,14 +4,12 @@ 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] 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]
+See also: [square_language], [composite_word_language]
Aliases: primitive words language
diff --git a/repetitive_string b/repetitive_string
@@ -0,0 +1,7 @@
+# Repetitive string
+
+A [word] containing a nonempty [square_word] as a [factor]
+
+Up: [square_word]
+
+See also: [square_free_word], [repetitive_string_language]
diff --git a/repetitive_string_language b/repetitive_string_language
@@ -0,0 +1,11 @@
+# Repetitive string language
+
+The [formal_language] of [repetitive_strings]
+
+On alphabets of size at most 2, it is a [regular_language]
+
+On an alphabet of size at least 3, it is not [context_free]: shown in [ross1982repetitive]
+
+Up: [formal_language] of [repetitive_string]
+
+See also: [square_free_words_language]
diff --git a/square_free_word b/square_free_word
@@ -0,0 +1,9 @@
+# Square free word
+
+A [word] which does not contain a nonempty [factor] which is a [square], i.e.,a [word] which is not a [repetitive_string]
+
+Up: [word], [square]
+
+See also: [square_free_word_language], [repetitive_string]
+
+Aliases: square free words
diff --git a/square_free_word_language b/square_free_word_language
@@ -0,0 +1,13 @@
+# Square free word language
+
+The [formal_language] of [square_free_words]
+
+For an alphabet of size at most 2, it is a [finite_language]
+
+For an alphabet of size at least 3, by the [pumping_lemma_for_CFLs], it is not a [CFL]
+
+Up: [formal_language], [square_free_word]
+
+See also: [repetitive_string_language]
+
+Aliases: square free words language
diff --git a/square_word b/square_word
@@ -4,6 +4,6 @@ A [word] of the form uu
Up: [word]
-See also: [twin], [square_free_word], [square_language], [non_square_word]
+See also: [twin], [square_free_word], [square_language], [non_square_word], [repetitive_string]
Aliases: word square, word squares
