2005/028 - WFSM Auto-Intersection and join algorithms
Andre Kempe, Jean-Marc Champarnaud, Franck Guingne, Florent Nicart
FSMNLP 2005 (5th Int. wrokshop on finite state methods in natural language processing, Helsinki, Finland, September 1-2, 2005.
The join of two n-ary string relations is a main operation regarding to applications. The n-ary rational string relations are realized by weighted finite-state machines with n tapes. We provide an algorithm that computes the join of two machines via a more simple operation, the auto-intersection. The two operations generally do not preserve rationality. A delay-based algorithm is described for the case of a single tape pair, as well as the class of auto-intersections that it handles. It is generalized to multiple tape pairs and some enhancements are discussed.