wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

hopcrofts_algorithm (502B)

      1 # Hopcroft's algorithm
      2 
      3 https://fr.wikipedia.org/wiki/Algorithme_de_Hopcroft_de_minimisation_d%27un_automate_fini
      4 
      5 Constructs [myhill_nerode_equivalence] by successive refinement from the partition of states into [final_states] and [nonfinal_states];
      6 - looks like an optimized version of [Moore's_algorithm]
      7 
      8 most efficient known algorithm:
      9 - in O(s n log n)
     10   - for n the number of [states] of the [automaton]
     11   - and s the [alphabet] size
     12 
     13 Up: [minimization_automaton]
     14 
     15 See also: [Moore's_algorithm]