Rewrite rule gram mars with multitape automata

• Autorzy: Hulden M.

Identyfikatory

DOI

10.15398/jlm.v5i1.158

• Języki publikacji: EN

Abstrakty

EN

The majority of computational implementations of phonological and morphophonological alternations rely on composing together individual finite state transducers that represent sound changes. Standard composition algorithms do not maintain the intermediate representations between the ultimate input and output forms. These intermedia te strings, however, can be very helpful for various tasks: enriching information (indispensable for models of historical linguistics), providing new avenues to debugging complex grammars, and offering explicit alignment information between morphemes, sound segments, and tags. This paper describes a multitape automaton approach to creating full models of sequences of sound alternation that implement phonological and morphological grammars. A model and a practical implementation of multitape automata is provided together with a multitape composition algorithm tailored to the representation used In this paper. Practical use cases of the approach are illustrated through two common examples: a phonological example of a complex rewrite rule grammar where multiple rules interact and a diachronic ex ample of modeling sound change over time.

Słowa kluczowe

EN

grammar design; multitape automata; morphology; phonology; finite-state phonology

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Journal of Language Modelling
• Rocznik: 2017
• Tom: Vol. 5, No. 1
• Strony: 107--130
• Opis fizyczny: Bibliogr. 35 poz., rys., tab.

Twórcy

autor

Hulden M.

• Department of Linguistics, University of Colorado, USA

Bibliografia

• [1] Iñaki Alegria, Izaskun Etxeberria, Mans Hulden, and Montserrat Maritxalar (2010), Porting Basque morphological grammars to foma, an open-source tool, 6062: 105-113.
• [2] Mohamed Altantawy, Nizar Habash, Owen Rambow, and Ibrahim Saleh (2010), Morphological Analysis and Generation of Arabic Nouns: A Morphemic Functional Approach, in Proceedings of the Seventh International Conference on Language Resources and Evaluation (LREC’10), Valletta, Malta.
• [3] Robert S. P. Beekes (2011), Comparative Indo-European Linguistics: an Introduction, John Benjamins Publishing.
• [4] Kenneth R Beesley (1998), Constraining separated morphotactic dependencies in finite-state grammars, in Proceedings of the International Workshop on Finite State Methods in Natural Language Processing, pp. 118-127, Association for Computational Linguistics.
• [5] Kenneth R Beesley (2012), Kleene, a Free and Open-Source Language for Finite-State Programming, in 10th International Workshop on Finite State Methods and Natural Language Processing (FSMNLP), pp. 50-54.
• [6] Kenneth R Beesley and Lauri Karttunen (2000), Finite-state Non-Concatenative Morphotactics, in Proceedings of the 38th Annual Meeting on Association for Computational Linguistics.
• [7] Kenneth R. Beesley and Lauri Karttunen (2003), Finite State Morphology, CSLI Publications, Stanford, CA.
• [8] Noam Chomsky and Morris Halle (1968), The Sound Pattern of English, Harper & Row.
• [9] Ferdinand De Saussure (1879), Mémoire sur le système primitif des voyelles dans les langues indo-européennes, B.G. Teubner.
• [10] Dale Gerdemann and Mans Hulden (2012), Practical Finite State Optimality Theory, in Proceedings of the 10th International Workshop on Finite State Methods and Natural Language Processing, pp. 10-19, Association for Computational Linguistics, Donostia-San Sebastián.
• [11] Dale Gerdemann and Gertjan van Noord (2000), Approximation and exactness in finite state optimality theory, in Proceedings of the Fifth Workshop of the ACL Special Interest Group in Computational Phonology.
• [12] Nizar Habash and Owen Rambow (2006), MAGEAD: A Morphological Analyzer and Generator for the Arabic Dialects, in Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pp. 681-688, Association for Computational Linguistics, Sydney, Australia, doi: 10.3115/1220175.1220261, http://www.aclweb.org/anthology/P06-1086.
• [13] Nizar Habash, Owen Rambow, and George Kiraz (2005), Morphological analysis and generation for Arabic dialects, in Proceedings of the ACL Workshop on Computational Approaches to Semitic Languages, pp. 17-24, Association for Computational Linguistics.
• [14] Kenneth Hale (1973), Deep-surface canonical disparities in relation to analysis and change: An Australian example, Current trends in linguistics, 11: 401-458.
• [15] Bruce Hayes (2011), Introductory Phonology, John Wiley & Sons.
• [16] Mans Hulden (2006), Finite-State Syllabification, Lecture Notes in Artificial Intelligence, 4002: 86-96.
• [17] Mans Hulden (2009a), Finite-state Machine Construction Methods and Algorithms for Phonology and Morphology, Ph.D. thesis, University of Arizona.
• [18] Mans Hulden (2009b), Foma: a finite-state compiler and library, in Proceedings of the 12th conference of the European Chapter of the Association for Computational Linguistics,, pp. 29-32.
• [19] Mans Hulden (2009c), Regular Expressions and Predicate Logic in Finite-State Language Processing, in Jakub Piskorski, Bruce Watson, and Anssi Yli-Jyrä, editors, Finite-State Methods and Natural Language Processing-Post-proceedings of the 7th International Workshop FSMNLP 2008, volume 191 of Frontiers in Artificial Intelligence and Applications, pp. 82-97, IOS Press.
• [20] Mans Hulden (2009d), Revisiting multi-tape automata for Semitic morphological analysis and generation, Proceedings of the EACL 2009 Workshop on Computational Approaches to Semitic Languages, pp. 19-26.
• [21] Mans Hulden (2015), Grammar design with multi-tape automata and composition, in Proceedings of the The 12th International Conference on Finite-State Methods and Natural Language Processing (FSMNLP), Association for Computational Linguistics.
• [22] Ronald M. Kaplan and Martin Kay (1994), Regular models of phonological rule systems, Computational Linguistics, 20 (3): 331-378.
• [23] Lauri Karttunen (1998), The proper treatment of optimality theory In computational phonology, in Proceedings of the International Workshop on Finite State Methods in Natural Language Processing (FSMNLP).
• [24] Lauri Karttunen (2003), Computing with realizational morphology, In Computational Linguistics and Intelligent Text Processing, pp. 203-214, Springer.
• [25] Martin Kay (1987), Nonconcatenative Finite-State Morphology, in Proceedings of EACL 1987.
• [26] André Kempe, Franck Guingne, and Florent Nicart (2004), Algorithms for weighted multi-tape automata, XRCE Research Report 2004/031.
• [27] André Kempe and Lauri Karttunen (1996), Parallel replacement in finie state calculus, in Proceedings of the 34th annual meeting of the Association for Computational Linguistics.
• [28] Michael Kenstowicz and Charles Kisseberth (1979), Generative phonology, Academic Press.
• [29] George Anton Kiraz (2000), Multitiered nonlinear morphology using multitape finite automata: a case study on Syriac and Arabic, Computational Linguistics, 26 (1): 77-105.
• [30] George Anton Kiraz (2001), Computational nonlinear morphology: with emphasis on Semitic languages, Cambridge University Press, Cambridge.
• [31] Kimmo Koskenniemi (1983), Two-level morphology: A general computational model for word-form recognition and production, Publication 11, University of Helsinki, Department of General Linguistics, Helsinki.
• [32] Mehryar Mohri, Fernando Pereira, and Michael Riley (2002), Weighted finite-state transducers in speech recognition, Computer Speech & Language, 16 (1): 69-88.
• [33] Mehryar Mohri and Richard Sproat (1996), An efficient compiler for weighted rewrite rules, in Proceedings of the 34th annual meeting on Association for Computational Linguistics, pp. 231-238, Association for Computational Linguistics.
• [34] Erich Round (2011), Word final phonology in Lardil: Implications of an expanded data set, Australian Journal of Linguistics, 31 (3): 327-350.
• [35] Robert Lawrence Trask (1996), Historical Linguistics, Oxford University Press.