Revisiting Multi-Tape Automata for Semitic Morphological Analysis and Generation

What it is about

Root-and-pattern morphology fits a multi-tape automaton well, since the root, the vowel pattern, the template and the affixes can run on separate tapes. Hulden shows how to store such an automaton on a single tape that any standard finite-state toolkit can handle. Each tape symbol is marked with its tape number during construction, the tapes are interleaved with a blank symbol, and a homomorphism removes the markers at the end. Tape contents are generated as languages and then constrained by two-level-style rules, so that every root consonant must match an input consonant and a pattern vowel must match a vocalisation. The method is implemented in foma with a modified matcher and tested on Arabic verbs with about 2,000 roots. The paper notes that a naive 5-tape example has 5,056,506 transitions, which a few encoding tricks reduce to 97,126. With any trilateral root accepted, the Arabic grammar has about 2,000 states.

Ideas

• I1. Interleaved tape storage for Hebrew verb stems: the input letters, the root consonants, the stem pattern and the affixes aligned position by position. The segmenter tables of tools/hbo could be produced from such aligned tapes, so that each segment carries its root and pattern for the parser to use.
• I2. Optional vowels inside patterns (C(V)C(V)C), so that one grammar parses pointed, partly pointed and unpointed words. This is the natural way to unify the two modes of tools/hbo instead of keeping two grammars.
• I3. A baseline: accept any trilateral root first, record the automaton size and the number of spurious roots, then add a root list and measure again. The difference is the cost of the missing lexicon, a number Mova can report honestly.

For Mova

I1 goes into The verb (stem templates) and the segmenter of tools/hbo. I2 goes into 1. Script and pointing and the pointed/unpointed modes of tools/hbo. I3 is a measurement for tools/hbo. The same tape design is a candidate for Aramaic verbs in The verb in Biblical Aramaic.

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.3115/1621774.1621779

@inproceedings{hulden2009revisiting,
  title = {{Revisiting Multi-Tape Automata for Semitic Morphological Analysis and Generation}},
  author = {Hulden, Mans},
  booktitle = {Proceedings of the EACL 2009 Workshop on Computational Approaches to Semitic Languages},
  year = {2009},
  doi = {10.3115/1621774.1621779},
  url = {https://doi.org/10.3115/1621774.1621779}
}

References

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

1. Beesley, K. and Karttunen, L. (2003). Finite-State Morphology. CSLI, Stanford. find
2. Beesley, K. R. (1996). Arabic finite-state analysis and generation. In COLING ’96. find
3. Beesley, K. R. (1998a). Arabic morphology using only finite-state operations. In Proceedings of the Workshop on Computational Approaches to Semitic Languages COLING-ACL, pages 50– 57. find our card
4. Beesley, K. R. (1998b). Consonant spreading in Arabic stems. In ACL, volume 36, pages 117– 123. Association for Computational Linguistics. find
5. Beeston, A. F. L. (1968). Written Arabic: An approach to the basic structures. Cambridge University Press, Cambridge. find
6. Buckwalter, T. (2004). Arabic morphological analyzer 2.0. LDC. find
7. Habash, N. and Rambow, O. (2006). MAGEAD: A morphological analyzer and generator for the Arabic dialects. Proceedings of COLING-ACL 2006. find our card
8. Habash, N., Rambow, O., and Kiraz, G. (2005). Morphological analysis and generation for Arabic dialects. Proceedings of the Workshop on Computational Approaches to Semitic Languages (ACL ’05). find our card
9. Hulden, M. (2008). Regular expressions and predicate logic in finite-state language processing. find
10. In Piskorski, J., Watson, B., and Yli-Jyrä, A., editors, Proceedings of FSMNLP 2008. find
11. Kataja, L. and Koskenniemi, K. (1988). Finite-state description of Semitic morphology: a case study of ancient Akkadian. In COLING ’88, pages 313–315. find
12. Kay, M. (1987). Nonconcatenative finite-state morphology. In Proceedings of the third conference on European chapter of the Association for Computational Linguistics, pages 2–10. Association for Computational Linguistics. find
13. Kiraz, G. A. (1994). Multi-tape two-level morphology: A case study in Semitic non-linear morphology. In COLING ’94, pages 180–186. find our card
14. Kiraz, G. A. (2000). Multi-tiered nonlinear morphology using multitape finite automata: A case study on Syriac and Arabic. Computational Linguistics, 26(1):77–105. find
15. Kiraz, G. A. (2001). Computational nonlinear morphology: with emphasis on Semitic languages. Cambridge University Press, Cambridge. find
16. Koskenniemi, K. (1983). Two-level morphology: A general computational model for word-form recognition and production. Publication 11, University of Helsinki, Department of General Linguistics, Helsinki. find
17. Lavie, A., Itai, A., and Ornan, U. (1988). On the applicability of two level morphology to the inflection of Hebrew verbs. In Proceedings of ALLC III, pages 246–260. find
18. McCarthy, J. J. (1981). A Prosodic Theory of Non-concatenative Morphology. Linguistic Inquiry, 12(3):373–418. find
19. van Noord, G. (2000). FSA 6 Reference Manual. find
20. Wehr, H. (1979). A Dictionary of Modern Written Arabic. Spoken Language Services, Inc., Ithaca, NY. find
21. Yli-Jyrä, A. and Koskenniemi, K. (2004). Compiling contextual restrictions on strings into finite-state automata. The Eindhoven FASTAR Days Proceedings. find
22. Yona, S. and Wintner, S. (2008). A finite-state morphological grammar of Hebrew. Natural Language Engineering, 14(2):173–190. find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/aclbulk-2009-hulden-revisiting-multi-tape-automata-semitic/