DFA Minimization

Given a finite deterministic automaton (DFA) from a class $C$ of DFAs, determine its minimal automaton given by the equivalence relation on states.

Parameters

$n$ : number of states
$d$ : number of transitions
$k$ : size of alphabet

Related Problems

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 3 of 3 algorithms

				See more
Hopcroft's algorithm	1971	$O(kn \log n)$	$O(kn)$
Brzozowski's algorithm	1963	$O(2^n)$	$O(2^n)$
Moore's algorithm	1956	$O(n^2 k)$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table