Conclusion

We have discussed a number of variants of the subset-construction algorithm for determinising finite automata containing $\epsilon$-moves. The experiments support the following conclusions:

• The integrated variants per subset and per state work much better for automata containing a large number of $\epsilon$-moves. The per subset variant tends to improve upon the per state algorithm if the number of $\epsilon$-moves increases even further.
• We have identified four different variants of the per graph algorithm. In our experiments, the per graph^t is the algorithm of choice for automata containing few $\epsilon$ moves, because it is faster than the other algorithms, and because it produces smaller automata than the per graph^s and per graph^s,a variants.
• The per graph^t,c variant is an interesting alternative in that it produces the smallest results. This variant should be used if the input automaton is expected to contain many non-co-accessible states.
• Automata produced by finite-state approximation techniques tend to contain many $\epsilon$-moves. We found that for these automata the differences in speed between the various algorithms can be enormous. The per subset and per state algorithms are good candidates for this application.

We have attempted to characterize the expected efficiency of the various algorithms in terms of the number of jumps and the number of states in the input automaton. It is quite conceivable that other simple properties of the input automaton can be used even more effectively for this purpose. One reviewer suggests to use the number of strongly $\epsilon$-connected components (the strongly connected components of the graph of all $\epsilon$-moves) for this purpose. We leave this and other possibilities to a future occasion.