Computational Phonology: the Delaware School

AP&M 4218, Wednesdays 12-1:30pm, Spring 2017

Description

The immediate aim of this reading group is to get us up to speed on the computational phonology work of Jeff Heinz (Delaware, but soon-to-be at Stony Brook), Jane Chandlee (Haverford), and Adam Jardine (Rutgers). Because Chandlee and Jardine were students of Heinz at Delaware, I'll call this "the Delaware School" of computational phonology.

An aspirational aim of this reading group is to be sufficiently equipped to understand (and perhaps to begin to tackle) Heinz's "Hilbert Problem for Phonology", described in more detail here. Briefly, Heinz revives the question originally and famously posed by Kiparsky (1968) in the title of his paper, "How abstract is phonology?" Heinz restates the question this way: "How distinct can underlying forms be from surface forms?" Then, in an effort to "[place] the focus on the analytical principles that would lead a scientist towards, or away from, an abstract analysis," Heinz formulates the problem this way: "What principles determine whether an abstract analysis of the observable facts is warranted or not?"

Reading list

Week 1: introduction

Heinz, Jeffrey. 2011. Computational Phonology - Part I: Foundations and Computational Phonology - Part II: Grammars, Learning, and the Future. Language and Linguistics Compass 5.4, 140-152 and 153-168.

Supplementary material

Helpful reading (from Stacy): Jurafsky, Daniel, and James H. Martin. 2006. Computational Phonology. Ch. 10 of Speech and Language Processing: An introduction to natural language processing, computational linguistics, and speech recognition.
Helpful links (from Eric M.): Why are Polynomial Time Problems Considered Tractable, and Larger Times are Not?, Machine models and complexity measures - the last three parts, Best, worst and average case, Nondeterministic algorithm - Introduction and Use sections, NP (complexity) - Introduction & Equivalence of Definitions sections.
Rosen, Kenneth. 2012. Discrete Mathematics and Its Applications (7th ed.).
Jurafsky, Daniel, and James H. Martin. 2006. Speech and Language Processing: An introduction to natural language processing, computational linguistics, and speech recognition (2nd ed.); draft chapters of 3rd ed. in progress available here.

Weeks 2-3: foundation

Kaplan, Ronald, and Martin Kay. 1994. Regular models of phonological rule systems. Computational Linguistics 20, 331-378. (Commentary by Mark Liberman; commentary by Graeme Ritchie.)

Possible further reading

Johnson, C. Douglas. 1972. Formal aspects of phonological description. The Hague: Mouton. (1-up version; 2-up version.)
Mohri, Mehryar. 1997. Finite-State Transducers in Language and Speech Processing. Computational Linguistics 23.2, 269-311.
Rogers, James, Jeffrey Heinz, Margaret Fero, Jeremy Hurst, Dakotah Lambert, and Sean Wibel. 2013. Cognitive and Sub-Regular Complexity. In Glyn Morrill and Mark-Jan Nederhof (eds.), Formal Grammar (Lecture Notes in Computer Science vol. 8036), 90-108.
Heinz, Jeffrey, and William Idsardi. 2013. What Complexity Differences Reveal About Domains in Language. Topics in Cognitive Science 5.1, 111-131.
Rogers, James, and Geoffrey K. Pullum. 2011. Aural Pattern Recognition Experiments and the Subregular Hierarchy. Journal of Logic, Language and Information, 329-342.

Notes from Week 2 (from Eric M.)

General plan: Revisit discussion of Kaplan & Kay after getting more hands-on experience with making FSTs and reading a bit more about what motivates their use.
Mechanical practice with FSAs:

Chapter 10/sections 1,2 and 5 of SLP 3rd edition; there are also a handful of end-of-chapter exercises.

Consider using FOMA as a tool...

If desired, Chapter 2 of SLP 2nd edition has a bunch more exercises (with solutions available - see first result) and additional explanations.

Motivational reading:

Chapter 10 sections 3.1 (on finite state OT) and 6 (on learning) of SLP 3rd edition

Note: The second Heinz paper ('computational phonology part II') is probably worth revisiting if these two sections are intriguing.

Research-y question to pursue - chain shifts and FSTs:

Do FSTs (more specifically, the structure of FST diagrams or properties of/results about transducer composition) offer any insight into why chain shifts are the way they are or how they should be analyzed?

IIRC, someone is going to lead us through chapter 10/section 5 of SLP 3rd edition and someone is going to take the lead on walking people through FOMA next week.

Weeks 4-5: overview

Jeffrey Heinz. 2017. The computational nature of phonological generalizations. In Larry Hyman and Frans Plank (eds.), Phonological Typology.

Weeks 6-7: vowel harmony

Heinz, Jeffrey, and Regine Lai. 2013. Vowel Harmony and Subsequentiality. Proceedings of the 13th Meeting on the Mathematics of Language, 52-63.

Weeks 8-10: strict locality

Chandlee, Jane, and Jeffrey Heinz. To appear. Strict Locality and Phonological Maps. Linguistic Inquiry.
Chandlee, Jane, Jeffrey Heinz, and Adam Jardine. Submitted. Input Strictly Local Opaque Maps.

A bunch of readings we just won't get to, sadly

Heinz, Jeffrey, Chetan Rawal, and Herbert G. Tanner. 2011. Tier-based Strictly Local Constraints for Phonology. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, 58-64.
Fu, Jie, Jeffrey Heinz, and Herbert G. Tanner. 2011. An Algebraic Characterization of Strictly Piecewise Languages. Theory and Applications of Models of Computation (Lecture Notes in Computer Science vol. 6648), 252-263.
Chandlee, Jane, Angeliki Athanasopoulou, and Jeffrey Heinz. 2012. Evidence for Classifying Metathesis Patterns as Subsequential. Proceedings of the 29th West Coast Conference on Formal Linguistics, 303-309.
Chandlee, Jane, and Jeffrey Heinz. 2012. Bounded copying is subsequential: Implications for metathesis and reduplication. Proceedings of the 12th Meeting of the ACL Special Interest Group on Computational Morphology and Phonology, 42-51.
Lai, Regine. 2012. Domain Specificity in Learning Phonology. Doctoral Dissertation, University of Delaware.
Heinz, Jeffrey, and James Rogers. 2013. Learning Subregular Classes of Languages with Factored Deterministic Automata. Proceedings of the 13th Meeting on the Mathematics of Language, 64-71.
Jardine, Adam. 2014. Logic and the Generative Power of Autosegmental Phonology. Supplemental Proceedings of the 2013 Meeting on Phonology.
Jardine, Adam, Jane Chandlee, Rémi Eyraud, and Jeffrey Heinz. 2014. Very efficient learning of structured classes of subsequential functions from positive data. Proceedings of the Twelfth International Conference on Grammatical Inference, 94-108.
Chandlee, Jane, and Cesar Koirala. 2014. Learning local phonological rules. Proceedings of the 37th Penn Linguistics Conference.
Chandlee, Jane, and Adam Jardine. 2014. Learning phonological mappings by learning strictly local functions. Proceedings of the 2013 Annual Meeting on Phonology.
Chandlee, Jane, Rémi Eyraud, and Jeffrey Heinz. 2014. Learning Strictly Local Subsequential Functions. Transactions of the Association for Computational Linguistics 2, 491-503.
Jardine, Adam, and Jeffrey Heinz. 2015. A Concatenation Operation to Derive Autosegmental Graphs. Proceedings of the 14th Meeting on the Mathematics of Language, 139-151.
Jardine, Adam. 2016. Locality and non-linear representations in tonal phonology. Doctoral dissertation, University of Delaware.
Jardine, Adam. 2016. Computationally, tone is different. Phonology 33.2, 247-283. [Longer version.]
Jardine, Adam, and Jeffrey Heinz. 2016. Learning Tier-based Strictly 2-Local Languages. Transactions of the Association for Computational Linguistics 4, 87-98.
Jardine, Adam. 2016. Learning tiers for long-distance phonotactics. Proceedings of the 6th Conference on Generative Approaches to Language Acquisition North America, 60-72.
Chandlee, Jane, Adam Jardine, and Jeffrey Heinz. 2016. Learning repairs for marked structures. Proceedings of the 2014 Annual Meeting of Phonology.
McMullin, Kevin. 2016. Tier-based locality in long-distance phonotactics: learnability and typology. Doctoral dissertation, University of British Columbia.
McMullin, Kevin, and Gunnar Ólafur Hansson. 2016. Long-distance phonotactics as Tier-based Strictly 2-Local languages. Proceedings of the 2014 Annual Meeting on Phonology.
Jardine, Adam, and Kevin McMullin. To appear. Efficient Learning of Tier-based Strictly k-Local Languages. Proceedings of Language and Automata Theory and Applications, 11th International Conference.
Jardine, Adam. To appear. Autosegmental representations in Zigula and Shambaa. In Jeffrey Heinz (ed.), Doing Computational Phonology.
Jardine, Adam. Under review. The local nature of tone association patterns.