DescriptionThis dissertation develops a new theory of autosegmental locality for vowel harmony patterns. Vowelharmony (vh) is a type of pattern in which vowels within a word assimilate to a particular subsegmental feature. Phonological theory has proposed a variety of representational structures to describe the relationships between subsegmental features but little is known about the computational effects of these structures. In this dissertation I use Formal Language Theory, a subfield of computer science, to compare the computational complexity of vh patterns represented over strings and multi-tiered autosegmental representations (ARs). This comparison determines that multi-tiered ARs with “bottle brush” structures (Clements 1976; Hayes 1990; McCarthy 1988; Padgett 1995) are preferable to strings because they reduce the complexity of vh and create more concise descriptions of vh patterns. I extend Jardine (2016b)’s and Jardine (2017a)’s Autosegmental Strictly Local (ASL) to a new complexity class called ASLVH which encompasses vh patterns that are local over multi-tiered ARs. This new class crosscuts the established subregular stringset hierarchy (Heinz 2018; Heinz, Rawal, and Tanner 2011; Rogers et al. 2013; Rogers and Pullum 2011) because it includes patterns which when represented over strings are strictly local like in Akan, Bayinna Orochen, and Kinande; strictly piecewise like in Finnish; locally testable like in Tutrugbu; and it excludes the unattested first-last-harmony pattern which is star-free (Lai 2015; Jardine 2019). The ASLVH class encompasses vh patterns with both opaque and transparent vowels and predicts a new restriction on the locality of transparency. A contrast in the harmonic feature is shown to have no effect on the complexity of opaque vowels but it vastly increases the complexity of patterns with transparent vowels like the one in Eastern Meadow Mari.