Algorithms for Weighted multi-Tape Automata
Andre Kempe, Franck Guingne, Florent Nicart
This report defines various operations for weighted multi-tape automata (WMTAs) and describes algorithms
that have been implemented for those operations in the WFSC toolkit. Some algorithms are new, others are
known or similar to known algorithms. The latter will be recalled to make this report more complete and
self-standing. We present a new approach to multi-tape intersection, meaning the intersection of a number of
tapes of one WMTA with the same number of tapes of another WMTA. In our approach, multi-tape intersection
is not considered as an atomic operation but rather as a sequence of more elementary ones, which facilitates
its implementation. We show an example of multi-tape intersection, actually transducer intersection,
that can be compiled with our approach but not with several other methods that we analysed. To show the
practical relavance of our work, we include an example of application: the preservation of intermediate results
in transduction cascades.
*ERRATUM* [6/21/2006]: This report contains an incorrect algorithm for auto-intersection, due to a wrong assumption concerning some properties of multi-tape automata. A correct algorithm is given in: Kempe, Champarnaud, Eisner, Guingne, Nicart. 2006. A class of rational n-WFSM auto-intersections. In Farré, Litovski, Schmitz, (eds.), Proc. CIAA 05, vol. 3845 of LNCS, pp 188-198, Springer.
XRCE Technical Research Report 2004/031.
2004_031.pdf (233.82 kB)