DFA Minimization: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(4 intermediate revisions by the same user not shown)
Line 12: Line 12:
== Parameters ==  
== Parameters ==  


<pre>$n$: number of states
$n$: number of states
 
$d$: number of transitions
$d$: number of transitions
$k$: size of alphabet</pre>
 
$k$: size of alphabet


== Table of Algorithms ==  
== Table of Algorithms ==  
Line 29: Line 31:
|-
|-
| [[Brzozowski's algorithm (DFA Minimization DFA Minimization)|Brzozowski's algorithm]] || 1963 || $O({2}^n)$ || $O({2}^n)$ || Exact || Deterministic || [https://www.semanticscholar.org/paper/Canonical-regular-expressions-and-minimal-state-for-Brzozowski/94def4233e1e8f15bab72e82708a03fd37233b14 Time] & [http://www.cs.ru.nl/bachelors-theses/2017/Erin_van_der_Veen___4431200___The_Practical_Performance_of_Automata_Minimization_Algorithms.pdf Space]
| [[Brzozowski's algorithm (DFA Minimization DFA Minimization)|Brzozowski's algorithm]] || 1963 || $O({2}^n)$ || $O({2}^n)$ || Exact || Deterministic || [https://www.semanticscholar.org/paper/Canonical-regular-expressions-and-minimal-state-for-Brzozowski/94def4233e1e8f15bab72e82708a03fd37233b14 Time] & [http://www.cs.ru.nl/bachelors-theses/2017/Erin_van_der_Veen___4431200___The_Practical_Performance_of_Automata_Minimization_Algorithms.pdf Space]
|-
| [[Revuz's algorithm (Acyclic DFA Minimization DFA Minimization)|Revuz's algorithm]] || 1992 || $O(n)$ || $O(n)$ || Exact || Deterministic || [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/0304397592901423 Time] & [https://www.labri.fr/perso/zeitoun/research/pdf/Almeida-Zeitoun-IPL2008.pdf Space]
|-
| [[Almeida & Zeitoun (Cyclic Nontrivial SCCs DFA Minimization DFA Minimization)|Almeida & Zeitoun]] || 2008 || $O(n)$ || $O(n)$ || Exact || Deterministic || [https://www.labri.fr/perso/zeitoun/research/pdf/Almeida-Zeitoun-IPL2008.pdf Time & Space]
|-
|-
|}
|}


== Time Complexity graph ==  
== Time Complexity Graph ==  


[[File:DFA Minimization - Time.png|1000px]]
[[File:DFA Minimization - Time.png|1000px]]
== Space Complexity graph ==
[[File:DFA Minimization - Space.png|1000px]]
== Pareto Decades graph ==
[[File:DFA Minimization - Pareto Frontier.png|1000px]]

Latest revision as of 09:08, 28 April 2023

Description

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

Related Problems

Subproblem: Acyclic DFA Minimization, Cyclic Nontrivial SCCs DFA Minimization

Related: Cyclic Nontrivial SCCs DFA Minimization

Parameters

$n$: number of states

$d$: number of transitions

$k$: size of alphabet

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Hopcroft's algorithm 1971 $O(kn \log n)$ $O(kn)$ Exact Deterministic Time & Space
Moore's algorithm 1956 $O(n^{2} k)$ $O(n)$ Exact Deterministic Time
Brzozowski's algorithm 1963 $O({2}^n)$ $O({2}^n)$ Exact Deterministic Time & Space
Revuz's algorithm 1992 $O(n)$ $O(n)$ Exact Deterministic Time & Space
Almeida & Zeitoun 2008 $O(n)$ $O(n)$ Exact Deterministic Time & Space

Time Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination