کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429020 | 687005 | 2012 | 5 صفحه PDF | دانلود رایگان |
Minimization of deterministic finite automata has traditionally required complicated programs and correctness proofs, and taken O(nklogn) time, where n is the number of states and k the size of the alphabet. Here a short, memory-efficient program is presented that runs in O(n+mlogm), or even in O(n+mlogn), time, where m is the number of transitions. The program is complete with input, output, and the removal of irrelevant parts of the automaton. Its invariant-style correctness proof is relatively short.
► Efficient DFA minimization used to be complicated but is now made simple.
► Asymptotic running time is better than that of any publication prior to 2008.
► The given correctness proofs are invariant-style and rather brief.
► Complete program code is given, so there are no hidden issues.
Journal: Information Processing Letters - Volume 112, Issue 6, 15 March 2012, Pages 213–217