Comparison with the FSM library

We also provide the results for AT&T's FSM library again. FSM is designed to treat weighted automata for very general weight sets. The initial implementation of the library consisted of an on-the-fly computation of the epsilon-closures combined with determinisation. This was abandoned for two reasons: it could not be generalised to the case of general weight sets, and it was not outputting the intermediate epsilon-removed machine (which might be of interest in itself). In the current version $\epsilon$-moves must be removed before determinisation is possible. This mechanism thus is comparable to our per graph variant. Apparently, FSM employs an algorithm equivalent to our per graph^s,a. The resulting determinised machines are generally larger than the machines produced by our integrated variants and the variants which incorporate $\epsilon$-moves on the target side of transitions. The timings below are obtained for the pipe

$$\mbox{\tt fsmrmepsilon \vert fsmdeterminize }$$

This is somewhat unfair since this includes the time to write and read the intermediate machine. Even so, it is interesting to note that the FSM library is a constant factor faster than our per graph^s,a; for larger numbers of jumps the per state and per subset variants consistently beat the FSM library.