# Acyclic DFA Minimization (DFA Minimization)

Jump to navigation
Jump to search

## Description

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

## Related Problems

Generalizations: 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 |
---|---|---|---|---|---|---|

Revuz's algorithm | 1992 | $O(n)$ | $O(n)$ | Exact | Deterministic | Time & Space |