FST Concatenation


The idea of FST concatenation is quite simple, but the details of this method are rather complex, so we will not go into too much detail. In FST generation we have generated all Hwang-topology FSTs that fulfill certain necessary optimality conditions and therefore survived the pruning phase. In FST concatenation we will find a subset of these FSTs that span all the terminals, with a minimum length. Since we are interested in creating a SMT that is fulsome, we want to maximize the degree of the SMT, i.e. using as many FSTs as possible.

The applet shows a very simple example of FST Concatenation. Normally the amount of FSTs generated is approximately 4*n (for random generated instances), where n is the amount of terminals to be spanned. Furthermore the applet uses a rather naive and intuitive approach, whereas the fastest method currently available uses an Integer programming formulation, solved with branch-and-cut. So the applet is only for illustrative purpose, and does not show any actual algorithm.