Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-01-08T14:35:16.970Z Has data issue: false hasContentIssue false
  • English
  • Français

Formal and computational verification of phonological analyses*

Published online by Cambridge University Press:  14 August 2017

Mans Hulden
Mans Hulden*
Affiliation:
University of Colorado
*
E-mail: [email protected].
Get access Rights & Permissions [Opens in a new window]

Abstract

This article presents a selection of methods to analyse, compare, verify and formally prove properties about phonological generalisations. Drawing from both well-known and recent results in the domains of model checking and automata theory, a useful methodology for automating the task of comparing analyses and inventing counterexamples is explored. The methods are illustrated by practical case studies that are intended to both resolve concrete issues and be representative of typical techniques and results.

Type
Articles
Information
Phonology , Volume 34 , Issue 2 , August 2017 , pp. 407 - 435
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

Thanks to Dale Gerdemann, Mike Hammond and Lauri Karttunen for useful insights and discussion around various versions of this work. Thanks also to the editors and anonymous reviewers for many helpful comments and pointers. All errors are my own.

References

REFERENCES

Albro, Daniel M. (2005). Studies in computational Optimality Theory, with special reference to the phonological system of Malagasy. PhD dissertation, University of California, Los Angeles.Google Scholar
Anttila, Arto (1997). Deriving variation from grammar. In Hinskens, Frans, van Hout, Roeland & Wetzels, W. Leo (eds.) Variation, change and phonological theory. Amsterdam & Philadelphia: Benjamins. 35–68.CrossRefGoogle Scholar
Baier, Christel & Katoen, Joost-Pieter (2008). Principles of model checking. Cambridge, Mass.: MIT Press.Google Scholar
Beesley, Kenneth R. (2012). Kleene, a free and open-source language for finite-state programming. In Proceedings of the 10th International Workshop on Finite State Methods and Natural Language Processing. Association for Computational Linguistics. 50–54.Google Scholar
Beesley, Kenneth R. & Karttunen, Lauri (2003). Finite state morphology. Stanford: CSLI.Google Scholar
Bermúdez-Otero, Ricardo (2007). Diachronic phonology. In de Lacy, Paul (ed.) The Cambridge handbook of phonology. Cambridge: Cambridge University Press. 497–517.CrossRefGoogle Scholar
Bird, Steven (1995). Computational phonology: a constraint-based approach. Cambridge: Cambridge University Press.Google Scholar
Blattner, Meera & Head, Tom (1977). Single-valued a-transducers. Journal of Computer and System Sciences 15. 310–327.CrossRefGoogle Scholar
Boersma, Paul (1999). Optimality-Theoretic learning in the Praat program. Proceedings of the Institute of Phonetic Sciences of the University of Amsterdam 23. 17–35.Google Scholar
Chandlee, Jane, Eyraud, Rémi & Heinz, Jeffrey (2014). Learning Strictly Local subsequential functions. Transactions of the Association for Computational Linguistics 2. 491–503.Google Scholar
Culik II, K. (1978). Some decidability results about regular and push down translations. Research Report CS-78-09, University of Waterloo, Ontario. Available (May 2017) at https://cs.uwaterloo.ca/research/tr/1978/CS-78-09.pdf.Google Scholar
Eisner, Jason (2002). Comprehension and compilation in optimality theory. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics. 56–63.Google Scholar
Elenbaas, Nine (1999). A unified account of binary and ternary stress: considerations from Sentani and Finnish. PhD dissertation, Utrecht University.Google Scholar
Elenbaas, Nine & Kager, René (1999). Ternary rhythm and the lapse constraint. Phonology 16. 273–329.CrossRefGoogle Scholar
Ellison, T. Mark (1994). Phonological derivation in Optimality Theory. In Proceedings of the 15th International Conference on Computational Linguistics (COLING) . Association for Computational Linguistics. 1007–1013.CrossRefGoogle Scholar
Frank, Robert & Satta, Giorgio (1998). Optimality Theory and the generative complexity of constraint violability. Computational Linguistics 24. 307–315.Google Scholar
Gerdemann, Dale & Hulden, Mans (2012). Practical finite state Optimality Theory. In Proceedings of the 10th International Workshop on Finite State Methods and Natural Language Processing. Association for Computational Linguistics. 10–19.Google Scholar
Gerdemann, Dale & van Noord, Gertjan (2000). Approximation and exactness in finite state optimality theory. In Jason Eisner, Lauri Karttunen & Alain Thériault (eds.) Finite-state phonology: proceedings of the 5th Workshop of the ACL Special Interest Group in Computational Phonology (SIGPHON). Luxemburg. 34–45.Google Scholar
Griffiths, T. V. (1968). The unsolvability of the equivalence problem for Λ-free nondeterministic generalized machines. Journal of the ACM 15. 409–413.Google Scholar
Hakulinen, Auli, Korhonen, Riitta, Vilkuna, Maria & Koivisto, Vesa (2004). Iso suomen kielioppi. [Comprehensive Finnish grammar.] Helsinki: Suomalaisen kirjallisuuden seura.Google Scholar
Halle, Morris & Idsardi, William J. (2000). Stress and length in Hixkaryana. The Linguistic Review 17. 199–218.Google Scholar
Halle, Morris & Nevins, Andrew (2009). Rule application in phonology. In Raimy, Eric & Cairns, Charles E. (eds.) Contemporary views on architecture and representations in phonology. Cambridge, Mass.: MIT Press. 355–382.Google Scholar
Hammond, Michael (1997). Parsing syllables: modeling OT computationally. Ms, University of Arizona. Available as ROA-222 from the Rutgers Optimality Archive.Google Scholar
Hayes, Bruce, Tesar, Bruce & Zuraw, Kie (2013). OTSoft 2.3.2. Software package. http://www.linguistics.ucla.edu/people/hayes/otsoft/.Google Scholar
Heinz, Jeffrey (2009). On the role of locality in learning stress patterns. Phonology 26. 303–351.CrossRefGoogle Scholar
Heinz, Jeffrey & Idsardi, William J. (2011). Sentence and word complexity. Science 333. 295–297.Google Scholar
Hopcroft, John (1971). An n log n algorithm for minimizing states in a finite automaton. Technical Report STAN-CS-71-190, Computer Science Department, Stanford University.Google Scholar
Hopcroft, John E. & Ullman, Jeffrey D. (1979). Introduction to automata theory, languages, and computation. Boston: Addison-Wesley.Google Scholar
Hulden, Mans (2006). Finite-state syllabification. In Yli-Jyrä, Anssi, Karttunen, Lauri & Karhumäki, Juhani (eds.) Finite-state methods and natural language processing. Berlin & Heidelberg: Springer. 86–96.CrossRefGoogle Scholar
Hulden, Mans (2009a). Finite-state machine construction methods and algorithms for phonology and morphology. PhD dissertation, University of Arizona.Google Scholar
Hulden, Mans (2009b). Foma: a finite-state compiler and library. In Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics: demonstrations session. Association for Computational Linguistics. 29–32.CrossRefGoogle Scholar
Hulden, Mans (2009c). Regular expressions and predicate logic in finite-state language processing. In Piskorski, Jakub, Watson, Bruce & Yli-Jyrä, Anssi (eds.) Finite-state methods and natural language processing: post-proceedings of the 7th international workshop FSMNLP 2008. Amsterdam: IOS. 82–97.Google Scholar
Hulden, Mans (2015). Grammar design with multi-tape automata and composition. In Proceedings of the 12th International Conference on Finite State Methods and Natural Language Processing. Association for Computational Linguistics.Google Scholar
Idsardi, William J. (2000). Clarifying opacity. The Linguistic Review 17. 337–350.Google Scholar
Johnson, C. Douglas (1972). Formal aspects of phonological description. The Hague: Mouton.CrossRefGoogle Scholar
Kager, René (1999). Optimality Theory. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Kaplan, Ronald & Kay, Martin (1994). Regular models of phonological rule systems. Computational Linguistics 20. 331–378.Google Scholar
Karttunen, Lauri (1995). The replace operator. In Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics. 16–23.Google Scholar
Karttunen, Lauri (1996). Directed replacement. In Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics. 108–115.Google Scholar
Karttunen, Lauri (1998). The proper treatment of optimality in computational phonology. In Karttunen, Lauri & Oflazer, Kemal (eds.) Proceedings of the International Workshop on Finite State Methods in Natural Language Processing. Ankara: Bilkent University. 1–12.Google Scholar
Karttunen, Lauri (2006a). A finite-state approximation of optimality theory: the case of Finnish prosody. In Salakoski, Tapio, Ginter, Filip, Pyysalo, Sampo & Pahikkala, Tapio (eds.) Advances in natural language processing. Berlin & Heidelberg: Springer. 4–15.Google Scholar
Karttunen, Lauri (2006b). The insufficiency of paper-and-pencil linguistics: the case of Finnish prosody. Available as ROA-818 from the Rutgers Optimality Archive.Google Scholar
Karvonen, Daniel Howard (2005). Word prosody in Finnish. PhD dissertation, University of California, Santa Cruz.Google Scholar
Kiparsky, Paul (2003). Finnish noun inflection. In Nelson, Diane & Manninen, Satu (eds.) Generative approaches to Finnic and Saami linguistics. Stanford: CSLI. 109–161.Google Scholar
Kisseberth, Charles W. (1970). On the functional unity of phonological rules. LI 1. 291–306.Google Scholar
Koskenniemi, Kimmo (1983). Two-level morphology: a general computational model for word-form recognition and production. Helsinki: Department of General Linguistics, University of Helsinki.Google Scholar
Langendoen, D. Terence (1981). The generative capacity of word-formation components. LI 12. 320–322.Google Scholar
McCarthy, John J. (2003). Comparative markedness. Theoretical Linguistics 29. 1–51.Google Scholar
McCarthy, John J. & Prince, Alan (1993). Generalized alignment. Yearbook of Morphology 1993. 79–153.Google Scholar
Mohri, Mehryar & Sproat, Richard (1996). An efficient compiler for weighted rewrite rules. In Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics. 231–238.Google Scholar
Moore, Edward F. (1956). Gedanken-experiments on sequential machines. In Shannon, C. E. & McCarthy, J. (eds.) Automata studies. Vol. 2. Princeton: Princeton University Press. 129–153.Google Scholar
Myhill, John (1957). Finite automata and the representation of events. Technical Report 57-624, Wright Airport Development Command. 112–137.Google Scholar
Prince, Alan & Smolensky, Paul (1993). Optimality Theory: constraint interaction in generative grammar. Ms, Rutgers University & University of Colorado, Boulder. Published 2004, Malden, Mass. & Oxford: Blackwell.Google Scholar
Rabin, M. O. & Scott, D. (1959). Finite automata and their decision problems. IBM Journal of Research and Development 3. 114–125.Google Scholar
Riggle, Jason (2004). Generation, recognition, and learning in finite-state Optimality Theory. PhD dissertation, University of California, Los Angeles.Google Scholar
Rogers, James & Pullum, Geoffrey K. (2011). Aural pattern recognition experiments and the subregular hierarchy. Journal of Logic, Language and Information 20. 329–342.Google Scholar
Rubach, Jerzy (1984). Cyclic and Lexical Phonology: the structure of Polish. Dordrecht: Foris.Google Scholar
Rubach, Jerzy (2000). Glide and glottal stop insertion in Slavic languages: a DOT analysis. LI 31. 271–317.Google Scholar
Salomaa, Arto (1993). Decidability in finite automata. In Rozenberg, G. & Salomaa, A. (eds.) Current trends in theoretical computer science: essays and tutorials. Singapore: World Scientific. 572–578.Google Scholar
Vaillette, Nathan (2004). Logical specification of finite-state transductions for natural language processing. PhD dissertation, Ohio State University.Google Scholar
Yli-Jyrä, Anssi (2013). On finite-state tonology with autosegmental representations. In Proceedings of the 11th International Conference on Finite State Methods and Natural Language Processing. Stroudsburg, PA: Association for Computational Linguistics. 90–98.Google Scholar
Yli-Jyrä, Anssi & Koskenniemi, Kimmo (2007). A new method for compiling parallel replace rules. In Holub, Jan & Jan Žd’árek (eds.) Implementation and application of automata. Berlin & Heidelberg: Springer. 320–321.Google Scholar
Supplementary material: PDF

Hulden supplementary material

Hulden supplementary material 1

Download Hulden supplementary material(PDF)
PDF 28.8 KB
Supplementary material: File

Hulden supplementary material

Hulden supplementary material 2

Download Hulden supplementary material(File)
File 8.2 KB