Through an examination of vowel harmony and similar phenomena, we attempt to
define a lower boundary on the computational power of phonological rules. We formalize locality and discover that the conditions in rules interact in interesting ways.
We also provide a unified analysis for neutral vowels in harmony processes. The focus on computation allows for simplification in models of representation. This is an extended version of a paper that appeared as F. Mailhot and C. Reiss. Computing long-distance dependencies in vowel harmony. Biolinguistics, 1(1):28–48, 2007.