WFSM Auto-Intersection and join algorithms
Andre Kempe, Jean-Marc Champarnaud, Franck Guingne, Florent Nicart
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.
FSMNLP 2005 (5th Int. wrokshop on finite state methods in natural language processing, Helsinki, Finland, September 1-2, 2005.