Incremental DFA minimisation∗
Accepted: 11 December 2013
We present a new incremental algorithm for minimising deterministic finite automata. It runs in quadratic time for any practical application and may be halted at any point, returning a partially minimised automaton. Hence, the algorithm may be applied to a given automaton at the same time as it is processing a string for acceptance. We also include some experimental comparative results.
Mathematics Subject Classification: 68Q45 / 68Q65 / 68Q25
Key words: Regular languages / finite automata / minimisation algorithms
© EDP Sciences 2014