Recent work in formal language theory (Heinz & Lai 2013, Chandlee 2014, Jardine 2016, Heinz 2018, among many others) has aimed to classify phonological patterns in terms of the computational complexity of the functions required to express those patterns. Much attention has been focused on the significant boundary between two classes of functions: the non-deterministic functions, at the outer edge of the class of functions that can be described with finite-state transducers, and the more restrictive weakly deterministic functions, first identified and defined by Heinz & Lai (2013). The distinction between these two classes of functions is significant because it has been claimed that all of phonology (Heinz 2011), or at least all of segmental (= non-tonal) phonology (Jardine 2016), is subregular, meaning at most weakly deterministic.
I have three goals in this talk within this context. The first goal is to illustrate distinctions among relevant classes of functions via the analysis of vowel harmony patterns from four languages (Turkish, Maasai, Tutrugbu, and Turkana). The second goal is to show that non-deterministic segmental phonological patterns do indeed exist, given the vowel harmony patterns of Tutrugbu and Turkana. The third goal is to provide a definition of weakly deterministic functions based on a notion of interaction familiar from ordering in rule-based phonology that -- unlike Heinz & Lai’s (2013) definition, which ours subsumes -- properly classifies the Turkana pattern as non-deterministic.