commit 9a464ad675f4a4d4437e87833f8f34633e7c6a1b
parent 83f4b5de7712cd02ee4f53979d071bddb2b9769f
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 21 Feb 2025 12:05:20 +0100
commit with codex
Diffstat:
10 files changed, 62 insertions(+), 5 deletions(-)
diff --git a/factor b/factor
@@ -1,12 +1,16 @@
# Factor
-Definition: [word] u is factor of [word] v if we have v = xuy for some [word]s x and y
+Definition: [word] u is factor of [word] v if we have v = xuy for some [words] x and y
- [factor_universal]
- [absent_factor]
If u is a factor of v, then v is an [extension] of u
+- [factor_closed_language]
+- [factor_convex_language]
+- [factor_free_language]
+
Up: [formal_language_theory]
See also: [subword], [prefix], [suffix]
diff --git a/factor_closed_language b/factor_closed_language
@@ -0,0 +1,9 @@
+# Factor closed language
+
+A [formal_language] L such that, if u is in L and v is a [factor] of u, then v is in L
+
+Also closed "bifix-closed", because it is equivalent to being [prefix_closed] and [suffix_closed]
+
+Up: [factor]
+
+See also: [factor_convex_language], [Prefix_closed_language], [Suffix_closed_language], [factor_free_language], [bifix_free_language], [bifix_convex_language]
diff --git a/locally_testable_language b/locally_testable_language
@@ -1,21 +1,23 @@
# Locally testable language
-A [formal_language] is locally testable if it is k-testable for some k, where a k-testable language is one where membership depends only on the prefix and suffix of length k and the set of infixes of size k
+A [formal_language] is *locally testable* if it is k-testable for some k, where a k-testable language is one where membership depends only on the [prefix] and [suffix] of length k and the set of [factors] of size k
## Subclass
-- "strictly locally testable" in [caron2000families]: the locally testable languages are the Boolean combinations of strictly locally testable languages
+- "strictly locally testable" in [caron2000families]: the locally testable languages are the [Boolean_combinations] of [strictly_locally_testable_languages]
## Membership problem to the class
-Membership is decidable in [ptime] with algebraic characterization, cf [schutzenberger1965monoids], [caron2000families]
+The [membership_problem] is decidable in [PTIME] with an [algebraic_characterization], cf [schutzenberger1965monoids], [caron2000families]
## Generalizations
- [locally_threshold_testable_language] where you can count infixes up to some threshold
-- mTT+MOD dans [place2013separating], where you can further count [modulo] a certain value
+- mTT+MOD in [place2013separating], where you can further count [modulo] a certain value
- [garcia2000right]: [locally_testable_language_right] and [locally_testable_language_left], which strictly generalize the locally testable languages
See also: [piecewise_testable_language], [local_language], [suffix_testable_language], [prefix_testable_language]
Up: [formal_language]
+
+Aliases: locally testable languages
diff --git a/prefix b/prefix
@@ -3,6 +3,9 @@
- [prefix_u1]
- [prefix_code]
- [prefix_suffix_query]
+- [prefix_closed_language]
+- [prefix_convex_language]
+- [prefix_free_language]
Up: [formal_language_theory]
diff --git a/prefix_closed_language b/prefix_closed_language
@@ -0,0 +1,9 @@
+# Prefix closed language
+
+A [formal_language] where, if v is in L and u is a [prefix] of v, then u is in L
+
+Up: [prefix]
+
+Aliases: language prefix closed
+
+See also: [suffix_closed_language], [prefix_convex_language]
diff --git a/prefix_free_language b/prefix_free_language
@@ -0,0 +1,9 @@
+# Prefix free language
+
+A [formal_language] L is *prefix-free* if, whenever u and v are in L and u is a [prefix] of v, then u = v
+
+Up: [prefix]
+
+See also: [suffix_free_language], [bifix_free_language]
+
+Aliases: prefix free
diff --git a/subword b/subword
@@ -8,6 +8,9 @@ must be contiguous, unlike [subsequence]
- [longest_common_subword] [timkovsky1989complexity]
- [shortest_common_superword] [timkovsky1989complexity]
+- [subword_closed_language]
+- [subword_free_language]
+- [subword_convex_language]
Up: [formal_language_theory]
diff --git a/suffix b/suffix
@@ -5,6 +5,8 @@
- [suffix]
- [suffix_free_language]
- [suffix_testable_language]
+- [suffix_closed_language]
+- [suffix_convex_language]
Up: [formal_language_theory]
diff --git a/suffix_closed_language b/suffix_closed_language
@@ -0,0 +1,7 @@
+# Suffix closed language
+
+A [formal_language] where, if u is in L and v is a [suffix] of u, then v is in L
+
+Up: [suffix]
+
+See also: [Prefix_closed_language], [suffix_convex_language]
diff --git a/suffix_free_language b/suffix_free_language
@@ -0,0 +1,9 @@
+# Suffix free language
+
+A [formal_language] L is *suffix-free* if, whenever u and v are in L and u is a [suffix] of v, then u = v
+
+Up: [suffix]
+
+See also: [prefix_free_language], [bifix_free_language]
+
+Aliases: suffix free
