wiki_research

commit c0c2bdcd08776ed9d800b42c414985f4da279b3d
parent 367e8cf9115521c68533dc2e90fdcc2231f35f8d
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Mon,  1 Sep 2025 21:40:05 +0200

commit with codex

Diffstat:
brzozowskis_algorithm
 | 
4
+++-
dfa_minimization
 | 
9
+++++++++
equivalence_class
 | 
7
+++++++
formal_language_theory
 | 
1
+
hopcrofts_algorithm
 | 
2
+-
minimization_automaton
 | 
7
++-----
moores_algorithm
 | 
2
+-
myhill_nerode_equivalence
 | 
2
+-
myhill_nerode_theorem
 | 
9
+++++++++

9 files changed, 34 insertions(+), 9 deletions(-)
diff --git a/brzozowskis_algorithm b/brzozowskis_algorithm
@@ -1,5 +1,7 @@
 # Brzozowski's algorithm
 
+https://fr.wikipedia.org/wiki/Algorithme_de_Brzozowski_de_minimisation_d%27un_automate_fini
+
 [Algorithm] for [automaton_minimization].
 
 Take [automaton_mirror] then [determinize] then take [automaton_mirror] then [determinize]
@@ -7,4 +9,4 @@ Take [automaton_mirror] then [determinize] then take [automaton_mirror] then [de
 - [complexity_generic] studied in [defeclice2013brzozowski]:
   - [super_polynomial] on [automata_random]
 
-Up: [minimization_automaton]
+Up: [minimization_DFAs]
diff --git a/dfa_minimization b/dfa_minimization
@@ -0,0 +1,9 @@
+# DFA minimization
+
+- [brzozowskis_algorithm]
+- [hopcrofts_algorithm]
+- [moores_algorithm]
+
+Up: [minimization_automaton] of [DFA]
+
+Aliases: minimization DFAs
diff --git a/equivalence_class b/equivalence_class
@@ -0,0 +1,7 @@
+# Equivalence class
+
+A set of elements that are related by an [equivalence_relation]. Forms a [partition] of the set
+
+Up: [equivalence_relation]
+
+Aliases: equivalence classes
diff --git a/formal_language_theory b/formal_language_theory
@@ -53,6 +53,7 @@ Studies [formal_languages]
 - [ogdens_lemma]
 - [interchange_lemma] https://en.wikipedia.org/wiki/Interchange_lemma
   - other such results: https://cstheory.stackexchange.com/a/54032
+- [myhill_nerode_theorem]
 
 Up: [theoretical_computer_science]
 
diff --git a/hopcrofts_algorithm b/hopcrofts_algorithm
@@ -10,6 +10,6 @@ most efficient known algorithm:
   - for n the number of [states] of the [automaton]
   - and s the [alphabet] size
 
-Up: [minimization_automaton]
+Up: [minimization_DFAs]
 
 See also: [Moore's_algorithm]
diff --git a/minimization_automaton b/minimization_automaton
@@ -1,12 +1,9 @@
 # Minimization automaton
 
-- [brzozowskis_algorithm]
-  - https://fr.wikipedia.org/wiki/Algorithme_de_Brzozowski_de_minimisation_d%27un_automate_fini
-- [hopcrofts_algorithm]
-- [moores_algorithm]
+- for [DFAs]: [DFA_minimization]
 - for [NFAs]: [NFA_minimization]
 
-Up: [minimization]
+Up: [minimization] of [automaton]
 
 Aliases: minimization of automata, automata minimization, automaton minimization, minimization automata, automaton minimal, minimal automaton
 
diff --git a/moores_algorithm b/moores_algorithm
@@ -4,6 +4,6 @@ https://fr.wikipedia.org/wiki/Algorithme_de_Moore_de_minimisation_d%27un_automat
 
 Constructs [myhill_nerode_equivalence] by successive refinement from the partition of states into [final_states] and [nonfinal_states]
 
-Up: [minimization_automaton]
+Up: [minimization_DFAs]
 
 See also: [hopcrofts_algorithm]
diff --git a/myhill_nerode_equivalence b/myhill_nerode_equivalence
@@ -7,4 +7,4 @@ This is similar to [syntactic_congruence] but it only considers [right_extension
 
 Up: [dagstuhl_regular_expressions_matching_indexing_nicola]
 
-See also: [syntactic_congruence], [automaton_minimization]
+See also: [syntactic_congruence], [automaton_minimization], [myhill_nerode_theorem]
diff --git a/myhill_nerode_theorem b/myhill_nerode_theorem
@@ -0,0 +1,9 @@
+# Myhill nerode theorem
+
+https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem
+
+The [theorem] that says that a [formal_language] is a [regular_language] iff the [Myhill_nerode_equivalence] has a finite number of [equivalence_classes]
+
+Up: [formal_language_theory]
+
+See also: [Myhill_nerode_equivalence], [DFA_minimization]