A note on join and auto-intersection of n-ary rational relations
Andre Kempe, Jean-Marc Champarnaud, Jason Eisner
Multi-tape automata (MTAs) and weighted multi-tape automata (WMTAs) offer more advantages than one-tape and two-tape automata do. Multi-tape intersection plays an important role in the work with MTAs and WMTAs. It means the intersection of several tapes of one WMTA with the same number of tapes of another one.
The article analyzes and discusses theoretical and algorithmic problems that occur in multi-tape intersection, and shows under which conditions and how those problems can be solved. By showing what is possible in theory, it attempts to provide a benchmark against which algorithms for multi-tape intersection can be measured.
In our approach to multi-tape intersection, the operation is split into more elementary ones. We show the advantage of this approach, and prove that it does not introduce any additional regularity problems.
Eindhoven FASTAR Days, 2004.
2004_045.pdf (305.85 kB)