Algorithms for the join and auto-intersection of multi-tape weighted finite-state machines

A weighted finite-state machine with n tapes describes a rational relation on n strings. We recall some basic operations on n-ary rational relations, recast the important join operation in terms of "auto-intersection", and propose restricted algorithms for both operations. If two rational relations are joined on more than one tape, it can unfortunately lead to non-rational relations with undecidable properties. As a consequence, there cannot be a fully general algorithm, able to compile any rational join or auto-intersection. We define a class of triples < A, i, j > for which we are able. to compile the auto-intersection of the machine A w.r.t. tapes i and j. We hope that this class is sufficient for many practical applications.