A class of rational n-WFSM Auto-Intersections
Andre Kempe, Jean-Marc Champarnaud, Jason Eisner, Franck Guingne, Florent Nicart
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
CIAA 2005, Sophia-Antipolis, France, June 27-29, 2005.
ciaa.pdf (183.11 kB)