Selected Operations, Algorithms, and Applications of n-Tape Weighted Finite-State Machines

What it is about

The paper recalls weighted finite-state machines that read n strings at once (n-WFSMs) and asks what they can do that acceptors (one tape) and transducers (two tapes) cannot. It covers the join and auto-intersection of n-tape relations, and notes that no general auto-intersection algorithm can exist, because it can encode Post's Correspondence Problem; a restricted class, with bounded delay between two tapes, can be compiled. Six applications are shown with the Xerox WFSC tool: Semitic morphology with a 4-tape lexicon (vowels, root, pattern and surface form), keeping intermediate results in transducer cascades, learning morphological rules, aligning lexicon entries, extracting acronyms, and finding cognates in a bilingual dictionary by joining a triple-tape dictionary with a grapheme-similarity machine. The paper gives no new measurements; it argues from the constructions.

Ideas

• I1. A 3-tape root-and-pattern machine for Hebrew verbs in The verb: tape 1 for vowels and binyan, tape 2 for the consonantal root, tape 3 for the surface form, so that any one tape can be the input and the others are generated. Test it on the forms in The weak verbs.
• I2. Keep the segmentation on a tape of its own through the pipeline in tools/hbo, so the later stages (gparse, macula prag) can read the prefix and suffix splits that an earlier stage made, without a second pass. Measure how many later errors come from a lost split.
• I3. Cognate search for Hebrew and Aramaic: join triples (Hebrew word, Aramaic word, gloss) from The lexicon of Biblical Aramaic with a weighted correspondence machine for the letters, and check the top pairs against known cognate sets.

For Mova

I1 goes into The verb and 07-weak-verbs.md. I2 is an architecture note for tools/hbo and the cascade in world. I3 is a test for The lexicon of Biblical Aramaic. The undecidability result is a reason to keep any Mova join to bounded cases.

Cite

The paper itself, not this card. BibTeX from the library's record of the work. arXiv 1104.5362

@misc{kempe2011selected,
  title = {{Selected Operations, Algorithms, and Applications of n-Tape Weighted Finite-State Machines}},
  author = {Kempe, Andre},
  year = {2011},
  eprint = {1104.5362},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1104.5362}
}

References

37 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. S. Aı̈t-Mokhtar and J.-P. Chanod. Incremental finite-state parsing. In Proc. 5th Int. Conf. ANLP, pages 72–79, Washington, DC, USA, 1997. find
2. K.R. Beesley and L. Karttunen. Finite State Morphology. CSLI Publications, Palo Alto, CA, 2003. find
3. M. Brent. An efficient, probabilistically sound algorithm for segmentation and word discovery. Machine Learning, 34:71–106, 1999. find
4. J.-M. Champarnaud, F. Guingne, A. Kempe, and F. Nicart. Algorithms for the join and auto-intersection of multi-tape weighted finite-state machines. Int. Journal of Foundations of Computer Science, 19(2):453–476, 2008. World Scientific. find
5. M. Creutz and K. Lagus. Unsupervised models for morpheme segmentation and morfology learning. ACM Transactions on Speech and Language Processing, 4(1), 2007. find
6. S. Eilenberg. Automata, Languages, and Machines, volume A. Academic Press, San Diego, 1974. find
7. C.C. Elgot and J.E. Mezei. On relations defined by generalized finite automata. IBM Journal of Research and Development, 9(1):47–68, 1965. find
8. C. Frougny and J. Sakarovitch. Synchronized rational relations of finite and infinite words. Theoretical Computer Science, 108(1):45–82, 1993. find
9. J. Goldsmith. Unsupervised learning of the morphology of a natural language. Computational Linguistics, 27:153–198, 2001. find
10. T. Harju and J. Karhumäki. The equivalence problem of multitape finite automata. Theoretical Computer Science, 78(2):347–355, 1991. find
11. P. Isabelle and A. Kempe. Automatic string alignment for finite-state transducers. Unpublished work, 2004. find
12. R.M. Kaplan and M. Kay. Regular models of phonological rule systems. Computational Linguistics, 20(3):331–378, 1994. find
13. L. Karttunen, T. Gaál, and A. Kempe. Xerox finite state complier. Online demo and documentation, 1998. Xerox Research Centre Europe, Grenoble, France. http://www.xrce.xerox.com/competencies/content-analysis/fsCompiler/. ↗
14. M. Kay. Nonconcatenative finite-state morphology. In Proc. 3rd Int. Conf. EACL, pages 2–10, Copenhagen, Denmark, 1987. find
15. A. Kempe. Acronym-meaning extraction from corpora using multitape weighted finite-state machines. Research report 2006/019, Xerox Research Centre Europe, Meylan, France, 2006. find
16. A. Kempe. Viterbi algorithm generalized for n-tape best-path search. In Proc. 8th Int. Workshop FSMNLP, Pretoria, South Africa, 2009. find
17. A. Kempe, C. Baeijs, T. Gaál, F. Guingne, and F. Nicart. WFSC – A new weighted finite state compiler. In O.H. Ibarra and Z. Dang, editors, Proc. 8th Int. Conf. CIAA, volume 2759 of LNCS, pages 108–119, Santa Barbara, CA, USA, 2003. Springer Verlag, Berlin, Germany. n-Tape Weighted Finite-State Machines André Kempe find
18. A. Kempe, J.-M. Champarnaud, and J. Eisner. A note on join and auto-intersection of n-ary rational relations. In B. Watson and L. Cleophas, editors, Proc. Eindhoven FASTAR Days, number 04–40 in TU/e CS TR, pages 64–78, Eindhoven, Netherlands, 2004. find
19. A. Kempe, J.-M. Champarnaud, J. Eisner, F. Guingne, and F. Nicart. A class of rational n-wfsm auto-intersections. In J. Farré, I. Litovski, and S. Schmitz, editors, Proc. 10th Int. Conf. CIAA, pages 266–274, Sophia Antipolis, France, 2005. find
20. A. Kempe, J.-M. Champarnaud, F. Guingne, and F. Nicart. Wfsm auto-intersection and join algorithms. In Proc. 5th Int. Workshop FSMNLP, Helsinki, Finland, 2005. find
21. A. Kempe, F. Guingne, and F. Nicart. Algorithms for weighted multi-tape automata. Research report 2004/031, Xerox Research Centre Europe, Meylan, France, 2004. find
22. G.A. Kiraz. Linearization of nonlinear lexical representations. In J. Coleman, editor, Proc. 3rd ACL SIG Computational Phonology, Madrid, Spain, 1997. find
23. G.A. Kiraz. Multitiered nonlinear morphology using multitape finite automata: a case study on Syriac and Arabic. Computational Lingistics, 26(1):77–105, March 2000. find our card
24. W. Kuich and A. Salomaa. Semirings, Automata, Languages. Number 5 in EATCS Monographs on Theoretical Computer Science. Springer Verlag, Berlin, Germany, 1986. find
25. S. Kumar and W. Byrne. A weighted finite state transducer implementation of the alignment template model for statistical machine translation. In Proc. Int. Conf. HLT-NAACL, pages 63–70, Edmonton, Canada, 2003. find
26. M. Mohri. Edit-distance of weighted automata. In Proc. 7th Int. Conf. CIAA, volume 2608 of LNCS, pages 1–23, Tours, France, 2003. Springer Verlag, Berlin, Germany. find
27. M. Mohri, F.C.N. Pereira, and M. Riley. A rational design for a weighted finite-state transducer library. LNCS, 1436:144–158, 1998. find
28. F. Nicart, J.-M. Champarnaud, T. Csáki, T. Gaál, and A. Kempe. Multi-tape automata with symbol classes. In O.H. Ibarra and H.-C. Yen, editors, Proc. 11th Int. Conf. CIAA, volume 4094 of LNCS, pages 126–136, Taipei, Taiwan, 2006. Springer Verlag. find
29. F.C.N. Pereira and M.D. Riley. Speech recognition by composition of weighted finite automata. In E. Roche and Y. Schabes, editors, Finite-State Language Processing, pages 431–453. MIT Press, Cambridge, MA, USA, 1997. find
30. A. Pirkola, J. Toivonen, H. Keskustalo, K. Visala, and K. Järvelin. Fuzzy translation of cross-lingual spelling variants. In Proc. 26th Annual Int. ACM SIGIR, pages 345–352, Toronto, Canada, 2003. find
31. E. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52:264–268, 1946. find
32. J. Pustejovsky, J. Casta no, B. Cochran, M. Kotecki, M. Morrell, and A. Rumshisky. Linguistic knowledge extraction from medline: Automatic construction of an acronym database. In Proc. 10th World Congress on Health and Medical Informatics (Medinfo 2001), 2001. find
33. M.O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2):114–125, 1959. find
34. A.L. Rosenberg. On n-tape finite state acceptors. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 76–81, 1964. find
35. A. Schwartz and M. Hearst. A simple algorithm for identifying abbreviation definitions in biomedical texts. In Proc. Pacific Symposium on Biocomputing (PSB-2003), 2003. find
36. R.A. Wagner and M.J. Fischer. The string-to-string correction problem. Journal of the Association for Computing Machinery, 21(1):168–173, 1974. find
37. S. Yeates, D. Bainbridge, and I.H. Witten. Using compression to identify acronyms in text. In Proc. Data Compression Conf. (DCC-2000), Snowbird, Utah, USA, 2000. (Also published in a longer form as Working Paper 00/01, Department of Computer Science, University of Waikato, January 2000). n-Tape Weighted Finite-State Machines find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/langstream-2011-kempe-selected-operations-algorithms-applications-n/