Version 1 of the question: I am looking for any correct $O(n)$ algorithm in the literature which will solve the DFA minimization problem referred to in the quote below from [Almeida & Zeitoun 2008]. Whether the algorithm works on strings or automata doesn't matter.

Version 2 of the question: What is the classical algorithm being referred to in the quote below? The closest I've been able to get from reference [9] in the quote is algorithm SCOPES on page 307, but that requires that $k$ be given as an argument.

Recall that the primitive root of a word $w$ is the shortest word $r$ such that $w = r^k$ for some $k$. It is easy to see that minimizing a cycle $s_0 \xrightarrow{a_0} s_1 \xrightarrow{a_2} \ldots \xrightarrow{a_k} s_0$ amounts to finding a primitive root of its associated circular word: this primitive root is itself a circular word, and the cycle associated to it is the minimal automaton of the original cycle. It is classical that this computation can be performed in linear time (see e.g. [9] for instance).

[Almeida & Zeitoun 2008] J. Almeida and M. Zeitoun. Description and analysis of a bottom-up DFA minimization algorithm. Inform. Process. Lett., 107(2):52–59, 2008.

[9] M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, 1994.

  • 1
    $\begingroup$ I think you can do this if you first create a suffix tree. I'll let you check the details. $\endgroup$ – D.W. May 18 '18 at 1:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.