Publications
Authors:
  • Andre Kempe , Jean-Marc Champarnaud , Franck Guingne , Florent Nicart
Citation:
FSMNLP 2005 (5th Int. wrokshop on finite state methods in natural language processing, Helsinki, Finland, September 1-2, 2005.
Abstract:
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.
Year:
2005
Report number:
2005/028