commit 6b199ff608cd29fa0b7d0481140a68f9598ce83e
parent b2ff30ab2a62525e7771946f33d3496fe111bfc0
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 5 Mar 2025 17:03:59 +0100
commit with codex
Diffstat:
22 files changed, 215 insertions(+), 6 deletions(-)
diff --git a/commutative_closure b/commutative_closure
@@ -0,0 +1,9 @@
+# Commutative closure
+
+The *commutative closure* of a [formal_language] L is the set of all [words] that admit a [permutation] in L
+
+[commutative_closure_does_not_preserve_regularity]: If L is a [regular_language], then the commutative closure is not necessarily a [regular_language]
+
+Up: [formal_language_closure_operation]
+
+See also: [language_commutative]
diff --git a/commutative_closure_does_not_preserve_regularity b/commutative_closure_does_not_preserve_regularity
@@ -0,0 +1,5 @@
+# Commutative closure does not preserve regularity
+
+If L is a [regular_language], then the commutative closure is not necessarily a [regular_language]!
+
+Up: [mathematical_observation] about [commutative_closure] and [regular_languages]
diff --git a/context_free_language b/context_free_language
@@ -8,4 +8,4 @@
Up: [language], [context_free_grammar]
-Aliases: context-free languages, context free languages, context-free language, CFL
+Aliases: context-free languages, context free languages, context-free language, CFL, CFLs
diff --git a/degree b/degree
@@ -8,3 +8,5 @@ In [directed_graphs], we can distinguish the [indegree] and [outdegree], respect
- [average_degree]
Up: [graph_basic_notions]
+
+See also: [bounded_degree]
diff --git a/derivative b/derivative
@@ -0,0 +1,11 @@
+# Derivative
+
+https://en.wikipedia.org/wiki/Brzozowski_derivative
+
+Given a [word] u and a [formal_language] L, the *derivative* of L by u, written u^{-1} L, is the set of [words] v such that we have uv in L
+
+We can also define the *derivative* of a [formal_language], cf [quotient_formal_language]
+
+See also: [variety]
+
+Up: [formal_language]
diff --git a/finite_simple_group b/finite_simple_group
@@ -0,0 +1,9 @@
+# Finite simple group
+
+A finite [group] is simple if it does not have non-trivial [normal_subgroups]
+
+[classification_of_finite_simple_groups]
+
+Up: [group], [finite]
+
+Aliases: finite simple groups
diff --git a/formal_language_closure_operation b/formal_language_closure_operation
@@ -0,0 +1,11 @@
+# Formal language closure operation
+
+Specific case: [regular_language_closure_operation]
+
+- [upwards_closure]
+- [downwards_closure]
+- [commutative_closure]
+
+Up: [closure_operation], [formal_language]
+
+See also: [formal_language_operator]
diff --git a/formal_language_mirror b/formal_language_mirror
@@ -0,0 +1,9 @@
+# Formal language mirror
+
+The mirror of a [formal_language] L is the language formed of the [mirrors] of the [words] of L
+
+Up: [formal_language_operator]
+
+Aliases: language mirror, mirror language
+
+See also: [commutative_closure]
diff --git a/formal_language_operator b/formal_language_operator
@@ -0,0 +1,22 @@
+# Formal language operator
+
+An [operator] that takes one or two [formal_languages] and creates a new [formal_language]
+
+- [boolean_operators]
+ - [language_union]
+ - [language_intersection]
+ - [language_complementation]
+- [concatenation]
+- [kleene_star]
+- [morphism] / [inverse_morphism]
+- [quotient_formal_language]
+ - see [derivative]
+- [wreath_product]
+- [semidirect_product]
+- [shuffle]
+- [formal_language_mirror]
+- [formal_language_closure_operation]: an operator that takes one [formal_language] and extends it by adding more [words] to it
+ - [upward_closure] / [downward_closure]
+ - [commutative_closure]
+
+Up: [formal_language], [operator]
diff --git a/group b/group
@@ -0,0 +1,23 @@
+# Group
+
+A *group* is an [algebraic_structure] which is like a [monoid] but additionally requires that each [element] has an [inverse]
+
+Types of groups:
+
+- [coxeter_groups]
+- [solvable_group]
+- [group_abelian]
+
+[Theorems]:
+
+- classification of [finite_simple_groups]
+- [feit_thompson] theorem
+
+Tools:
+
+- [cayley_graph]
+- [cayley_table]
+
+Up: [algebraic_structure], [mathematics]
+
+See also: [monoid], [group_language]
diff --git a/group_abelian b/group_abelian
@@ -1,5 +1,9 @@
# Group abelian
-[commutative]
+A [group] which is [commutative]
-Up: [group]
+Up: [group], [commutative]
+
+Aliases: abelian group, abelian groups
+
+See also: [language_commutative], [semiring_commutative]
diff --git a/language_commutative b/language_commutative
@@ -0,0 +1,9 @@
+# Commutative language
+
+- [regular_language_commutative]
+
+Up: [formal_language] which is [commutative]
+
+See also: [parikh_image], [Commutative_closure]
+
+Aliases: commutative language, commutative languages
diff --git a/language_complementation b/language_complementation
@@ -0,0 +1,7 @@
+# Language complementation
+
+The [complementation] of a [formal_language]
+
+Up: [complementation]
+
+Aliases: language complement
diff --git a/language_downwards_closed b/language_downwards_closed
@@ -0,0 +1,20 @@
+# Language downwards closed
+
+A [formal_language] is *downwards closed* if any [subword] of the [formal_language] is in the [formal_language]
+
+[ideal_decomposition]: every downward closed language is a finite [union] of [language_ideal] i.e. terms of the form
+
+ A_1^* {a_1, epsilon} ... A_k^*
+ where the A_i are subalphabets
+
+[language_downwards_closed_details]
+
+The [language_complement] of a downwards closed [formal_language] is a [upwards_closed_language].
+
+Testing the [automaton_equivalence] of two [NFAs] recognizing downwards closed languages is [coNP_complete], cf [bachmeier2014finite]
+
+Up: [regular_language_family]
+
+See also: [higmans_lemma], [downwards_closure], [language_factor_minimal], [language_upwards_closed], [ganardi2024directed]
+
+Aliases: downward closed language, downward closed languages, downwards closed language, downwards closed languages
diff --git a/mirror b/mirror
@@ -0,0 +1,9 @@
+# Mirror
+
+Given a [word] w = a_1 ... a_n, its mirror is w' = a_n ... a_1
+
+Up: [word]
+
+See also: [automata_reversal], [palindrome], [commutative_closure]
+
+Aliases: mirrors
diff --git a/normal_subgroup b/normal_subgroup
@@ -9,3 +9,5 @@ Can be used to build [quotient_group] by a [congruence_relation]: the equivalenc
When the group is [abelian_group], all subgroups are normal
Up: [finite_simple_group]
+
+Aliases: normal subgroups
diff --git a/packing_coloring b/packing_coloring
@@ -0,0 +1,9 @@
+# Packing coloring
+
+work with [bernardo]
+
+https://www.quantamagazine.org/the-number-15-describes-the-secret-limit-of-an-infinite-grid-20230420/
+
+Up: [mathematics]
+
+See also: [graph_coloring], [packing_problem]
diff --git a/parikh_image b/parikh_image
@@ -0,0 +1,16 @@
+# Parikh image
+
+The *Parikh image* of a [word] is the [vector] of the number of occurrences of the letters that it contains, and the *Parikh image* of a [formal_language] is the set of Parikh images of the [words] that it contains
+
+[Parikhs_theorem]: the Parikh images of [CFLs] and of [regular_languages] are the same!
+
+The Parikh image is not always [recognizable] even for a [regular_language]
+- https://cstheory.stackexchange.com/questions/46670/languages-whose-parikh-image-is-recognizable
+- it relates to [regular_languages] whose [commutative_closure] is also a [regular_language]
+ - cf [commutative_closure_does_not_preserve_regularity]
+
+Up: [formal_language_theory]
+
+See also: [language_commutative], [length]
+
+Aliases: parikh images
diff --git a/pathwidth b/pathwidth
@@ -3,7 +3,8 @@
like [treewidth] but for [tree_decomposition] which is a [path]
- [pathwidth_directed]
-- [pathwidth_approximation]
+- [pathwidth_computation]
+ - [pathwidth_approximation]
Up: [width_measure], [path]
diff --git a/pathwidth_computation b/pathwidth_computation
@@ -0,0 +1,12 @@
+# Pathwidth computation
+
+The [computational_problem] of computing the [pathwidth] of an input [graph]
+
+https://en.wikipedia.org/wiki/Pathwidth#Special_classes_of_graphs
+- Is [NP_complete] even on [bounded_degree] [planar_graphs]
+- Can be computed in [linear_time] for [trees] and [forests]
+- Can be computed in [polynomial_time] for [treelike] [graphs]
+
+- [pathwidth_approximation]
+
+Up: [computational_problem], [pathwidth]
diff --git a/shuffle b/shuffle
@@ -1,6 +1,9 @@
# Shuffle
+A [word] w is a *shuffle* of two [words] u and v if we can interleave the characters of u and v to form w. We can also define the *shuffle* of two [formal_languages] L and L' as the set of [words] w that are shuffles of a [word] of L and a [word] of L'
+
- [shuffle_square]
-- a finite set of [word] can be decomposed into at most one multiset of which it is the shuffle: see [berstel2002shuffle]
+- a finite set of [words] can be decomposed into at most one multiset of which it is the shuffle:
+ - see [berstel2002shuffle]
-Up: [formal_language_theory]
+Up: [formal_language_operator]
diff --git a/upwards_closure b/upwards_closure
@@ -0,0 +1,16 @@
+# Upwards closure
+
+For L a [formal_language], the *upwards closure* of L is the set of [words] w which are [supersequences] of a word of L
+
+For any [formal_language] L, the upwards closure is a [regular_language]: this uses [Higman's_lemma]
+
+The upwards closure is a [upwards_closed_language]: any [supersequence] of a [word] of the upwards closure is in the upwards closure
+
+- [upwards_closure_state_complexity]
+ - [upwards_closure_cfl_state_complexity]
+
+See also: [language_upwards_closed], [downwards_closure]
+
+Up: [formal_language_operator], [closure_operation] on [supersequences]
+
+Aliases: upward closure, superword closure
