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.

  • 1
    $\begingroup$ Somewhat related to cyclic automata, but also unary automata allow O(n) minimization see. $\endgroup$
    – Janmar
    Commented Feb 5 at 15:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.