Publications
Authors:
  • Andre Kempe , Jean-Marc Champarnaud , Jason Eisner , Franck Guingne , Florent Nicart
Citation:
CIAA 2005, Sophia-Antipolis, France, June 27-29, 2005.
Abstract:
Weighted finite-state machines with n tapes describe n-ary rational string relations. The join n-ary relation is very important regarding to application. It is shown how to compute it via a more simple operation, the auto-intersection. Join and auto-intersection generally do not preserve rationality. We define a class of triples(A,i,j) such that the auto-intersection of the machine A w.r.t. tapes i and j can be computed by a delay-based algorithm. We point out how to extend this class and hope that it is sufficient for many practical applications
Year:
2005
Report number:
2005/021
Attachments: