What is the most complicated kind of deterministic finite-state automaton that can be minimized in $O(n)$ time?
Here’s what I’ve been able to find so far:
- The acyclic case has been solved. So any acyclic DFA can be minimized in $O(n)$ time by the Revuz algorithm [2].
- As for cyclic automata, an automaton that is a simple cycle can be minimized in $O(n)$ time. A simple cyclic automaton has an underlying graph which is a cycle, and in particular, has states that can be named $1,2,3,…n$ and the only transitions allowed are $1 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 4, …, i \rightarrow i+1,…, n \rightarrow 1$. This is from Almeida and Zeitoun [1], who reference a result in Lemma 4.2 of their paper saying that the primitive root of a string can be found in $O(n)$ time.
Is this the state of the art, or can more complicated automata be minimized in $O(n)$ time?
[1] J. Almeida and M. Zeitoun. Description and analysis of a bottom-up DFA minimization algorithm. Inform. Process. Lett., 107(2):52–59, 2008.
[2] D. Revuz. Minimisation of acyclic deterministic automata in linear time. Theoret. Comput. Sci., 92:181–189, 1992.
