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?"

- 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. - 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.

- 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.) - 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. **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.

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

- Heinz, Jeffrey, and Regine Lai. 2013. Vowel Harmony and Subsequentiality.
*Proceedings of the 13th Meeting on the Mathematics of Language*, 52-63. - Gainor, Brian, Regine Lai, and Jeffrey Heinz. 2012. Computational Characterizations of Vowel Harmony Patterns and Pathologies.
*Proceedings of the 29th West Coast Conference on Formal Linguistics*, 63-71. - Lai, Regine. To appear. Learnable vs. Unlearnable Harmony Patterns.
*Linguistic Inquiry*.

- 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.
- Chandlee, Jane. 2014.
*Strictly Local Phonological Processes.*Doctoral dissertation, University of Delaware. - Chandlee, Jane, Rémi Eyraud, and Jeffrey Heinz. 2015. Output Strictly Local Functions.
*Proceedings of the 14th Meeting on the Mathematics of Language*, 112-125. - Chandlee, Jane, and Steven Lindell. To appear. A logical characterization of input strictly local functions. In Jeffrey Heinz (ed.),
*Doing Computational Phonology.*

- 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.