To better understand the limits of possible language patterns, early work in computational linguistics modeled patterns as sets of well-formed strings and classified patterns according to the machinery necessary for deciding whether a given string is well-formed, giving rise to what is known as the Chomsky Hierarchy of formal languages (Chomsky 1956). At the bottom of the Chomsky hierarchy are the finite languages, which can be modelled as finite sets of strings. Anything in the set is considered good and included in the language, whereas anything not in the set is considered bad and excluded from the language. The original Chomsky hierarchy distinguishes four classes above the finite languages. From least to most powerful, these are the regular languages, the context-free languages, the context-sensitive languages, and the recursively enumerable languages. Phonology is argued to be at most regular in terms of complexity (Johnson 1972; Kaplan & Kay 1994) but does not, in most cases, require the full capabilities of regular languages and functions. Accordingly, much work has divided the regular region into a hierarchy of subregular formal language classes (e.g., McNaughton & Papert 1971; Rogers & Pullum 2011; Rogers et al. 2013). Importantly, while formal languages are well-suited to static phonotactic patterns, they cannot directly model dynamic processes, and so a parallel hierarchy of functions and relations (i.e., collections of well-formed pairs of strings) is being explored as well. The remainder of this section provides an overview of two important classes of subregular languages: the Strictly Local (SL) languages that form the basis of the SL functions developed by Chandlee (2014) and Chandlee et al. (2014; 2015),1 as well as the Tier-based Strictly Local (TSL) languages developed by Heinz et al. (2011) that form the basis of the TSL functions explored in this paper.

SL languages can be defined positively or negatively, although negative definitions may be more intuitive to phonologists working in constraint-based frameworks like Optimality Theory (OT: Prince & Smolensky 2004) since they function like inviolable markedness constraints. From the negative perspective, SL languages ban particular contiguous sequences of up to a fixed length, excluding any string that contains one or more illegal contiguous sequences. When all the banned sequences are of length k or shorter, we say that the language is Strictly k-Local (SL_k). Many phonotactic patterns can be described as an SL_k language. For example, in Japanese the alveolar fricative [s] cannot occur immediately before the high front vowel [i]. Not only is the sequence *[si] absent from the language’s lexicon, but there are alternations that occur specifically to avoid it. One such alternation occurs when a verb root ending in /s/ is put into the past tense, as illustrated by the comparison of /hos-u/ → [hosu] ‘dry-NPST’ and /hos-ita/ → [hoɕita] ‘dry-PST’. This aspect of Japanese phonotactics can be captured by an SL₂ language that bans the sequence *[si], preventing strings such as *[hosita] from surfacing. The TSL languages augment the SL languages with intuitions from autosegmental phonology — originally developed by Goldsmith (1976) for the analysis of tonal phenomena — in order to describe non-local phonotactic restrictions. While the specifics of autosegmental analyses can differ, the approach can be distilled down to the following. First, a phonological form consists of multiple connected levels of representation called ‘tiers’. Second, a given phonological element (e.g., a feature or segment) can be present on one tier but absent on another. Third, material that is non-local on one tier may be local on another. Finally, only material that is local on the relevant tier matters when enforcing a pattern. This intuition that non-local configurations can be rendered local with the right representational choices forms the foundation of the TSL languages and functions at the center of this paper.

Despite the wide-ranging interest in tiers and their utility, it is only recently that their expressive power has been explored in the context of formal language theory (Heinz et al. 2011; Jardine & Heinz 2016; McMullin 2016; McMullin & Hansson 2016; Jardine & McMullin 2017; Lambert & Rogers 2020). From this perspective, a tier is a subset of the alphabet,2 and a Tier-based Strictly k-Local (TSL_k) language is a language that is SL_k once all non-tier elements have been erased. The result of erasing the non-tier elements from a string is often called the projection of that string onto the given tier. More sophisticated methods of projection that consider surrounding local material in addition to segment identity have been explored (Graf & Mayer 2018; Mayer & Major 2018; De Santo & Graf 2019), although we limit ourselves in this paper to the maximally simple means of projection where a segment’s identity is the only determining factor. A TSL language can then be said to ban a given string if that string’s projection onto the specified tier contains any impermissible contiguous sequences.

Consider the pattern of liquid harmony in Bukusu, where sequences of [⋯r⋯l⋯] are not permitted (Odden 1994; Hansson 2010a). Data for this pattern are provided in (1), which show that the applicative suffix appears as [-ira] if the nearest leftward liquid is [r], else it appears as [-ila]. The pattern can be expressed as a TSL₂ language banning the sequence *[rl] on the liquid tier T = {r, l}. Forms like *[rumila] are excluded, since projecting them to the liquid tier yields the illegal string *[rl]. Note that such a language model does not actually describe the apparent process of liquid harmony, just its result.

A good question to ask at this point is how an autosegmental analysis of liquid harmony compares to the TSL analysis just presented. Both make a distinction between a representational level where the whole phonological string is present and a representational level where only the liquid consonants are present. Also in both approaches, the prohibition against a contiguous sequence of [–lateral][+lateral] is enforced on the less-inclusive level of representation containing just liquids. Where the approaches differ concerns the way these levels of representation are defined. An autosegmental approach might postulate, for example, that there is a tier containing all and only the instances of the feature [±lateral]. Assuming that only liquid consonants can be specified for the feature [±lateral], the entities present on this [±lateral] tier will then always correspond to an [l] or [r] in the full phonological string. For its part, the TSL approach arbitrarily stipulates that there is a representational level including all and only the instances of [l] and [r]. While inspired by the autosegmental approach, the TSL perspective does not follow it to the letter, allowing us to gain insight into the formal underpinnings of the structures of long-distance phonology with minimal theoretical commitments. Although the tier of a TSL language can in principle be an arbitrary set of segments, TSL analyses are by no means incompatible with approaches that define tiers according to perceptual similarity (as in the Agreement by Correspondence framework; see e.g. Rose & Walker 2004 and Hansson 2010a) or according to feature geometry (Clements & Hume 1995). Many of the tiers used in the computational literature (and in our analyses below) happen to form a natural class relative to typical feature theories, and one can of course decide to limit themselves only to similarity-driven or feature-definable tiers, but there is formally no such requirement. However one chooses to restrict the types of tiers that are possible, that choice will not change the fact that TSL languages over those tiers still model the intuition that a non-local pattern can hold locally at an appropriate representational level. Despite their name, the TSL languages do not themselves provide a theory of possible tiers; rather, they provide a model of the effect that a tier (motivated or not) has upon the assessment of locality.

To model phonological processes we need to shift our focus from languages to functions that map input strings to output strings. While it is not as well understood as the subregular hierarchy of languages, the analogous subregular hierarchy of functions has seen many developments in recent years (Heinz 2018). Particularly important to this paper are the Input Strictly Local (ISL) functions and the Output Strictly Local (OSL) functions, which adapt the notion of strict locality to input-output maps (Chandlee 2014; Chandlee & Heinz 2018; Chandlee et al. 2018). Various equivalent characterizations of these functions exist. This paper will make use of their automata-theoretic characterization, representing processes with finite-state transducers (FSTs) that meet particular criteria. For the full details of this characterization see Chandlee (2014), Chandlee et al. (2014), and Chandlee et al. (2015).

A (one-way) FST produces an output string incrementally by reading an input string one element at a time in a single direction. Such a machine consists of a finite set of states (which can be thought of as a primitive sort of memory) and a finite set of transitions between these states (which include the machine’s instructions for what to write at each step). The machine begins in a designated initial state, and traverses a path through the state space by following transitions in response to the input that it reads. Figure 1 presents a visual diagram of an FST. States are represented with circles, with the initial state marked with an unlabeled incoming arrow. Transitions are represented with labelled arrows between states; a label ‘a:b’ is an instruction to take that transition when reading ‘a’ from the input and write ‘b’ to the output. The transducer in Figure 1 operates over the input alphabet {a, b}, transforming all odd-numbered positions to ‘a’ and all even-numbered positions to ‘b’. For example it maps /bab/ to [aba] and maps /aabbabbb/ to [abababab].

ISL and OSL FSTs have particular conditions on the state set and transitions. States in an ISL_k FST correspond to strings of up to k – 1 input symbols, whereas states in an OSL_k FST correspond to strings of up to k – 1 output symbols. Transitions in an ISL_k FST always go to the state matching the most recent k – 1 symbols that have been read from the input string, whereas the transitions in an OSL_k FST always go to the state that matches the most recent k – 1 symbols that have been written to the output string. Additionally, ISL and OSL FSTs are required to be deterministic, meaning that there is one transition per input element per state.

As a concrete example of these restrictions, consider the transducers in Figure 2, both of which compute the rule of post-nasal voicing in the Puyu Pungo dialect of Quechua (Orr 1962; Rice 1993). The transducers operate over simplified alphabets where ‘V’ represents a vowel, ‘N’ represents a nasal consonant, ‘T’ represents a voiceless obstruent, and ‘D’ represents a voiced obstruent. Data for the pattern are provided in (2).

In ISL and OSL transducers, the initial state corresponds to the empty string, which we write as λ. For maximum clarity, we write the labels of input-oriented FSTs between forward slashes (e.g., /X/) and the states of output-oriented FSTs between square brackets (e.g., [X]). Structurally, the crucial difference between the ISL and OSL analysis concerns the ‘T:D’ transitions that leave the ‘N’ states. These are depicted with dashed lines in the figures. This transition ends up in the /T/ state of the ISL transducer, but ends up in the [D] state of the OSL transducer. Despite the difference in structure, the FSTs compute the same function in this particular case (i.e., they are extensionally equivalent).

As mentioned at the outset, long-distance processes cannot be modeled by tracking only recent input/output as the SL functions do. Consider, for example, the sibilant harmony found in Aari and shown in (3). The perfective suffix /-s/, which stays faithful in (3a), surfaces instead as [-ʃ] when preceded (at any distance) by a lamino-postalveolar sibilant, as shown in (3b–f). The process is ‘asymmetric’ in that underlying /ʃ/ does not analogously become [s] when preceded by an alveolar fricative (Hansson 2010a: p. 357).

Figure 3 demonstrates what goes wrong when we attempt to model such a process as OSL for k = 2. For readability we use ‘s’ to represent [+ant] sibilants, ‘ʃ’ for [–ant] sibilants, and ‘&’ as a placeholder for all non-sibilant segments. According to the generalization, an input /s/ may be mapped in two different ways. Compare (3a) /baʔ-s-e/ → [baʔse] to (3e) /ʃed-er-s-it/ → [ʃederʃit]. In both cases, the FST will be in the state [&] when the underlying /s/ is read since the last element produced was a non-sibilant ([ʔ] in 3a and [r] in 3e). The output forms show, however, that these two /s/’s must be outputted differently, meaning the transducer would need both an ‘s:s’ and an ‘s:ʃ’ transition out of this state. These two transitions are depicted in Figure 3 with dashed lines. The requirement of determinism prevents the FST from including both of these transitions.

The problem, of course, is due to the long-distance nature of the process. The crucial distinction between (3a) and (3e) is that the former does not contain a prior sibilant but the latter does. That distinction cannot be made by an FST that only remembers the previous output segment. And since long-distance processes apply regardless of the number of intervening segments, simply increasing the locality window will not suffice. As such, we must pursue other means for characterizing long-distance phonological processes.

A well-studied aspect of long-distance phonological processes is the non-participation or transparency of material between the trigger and target (see, e.g., Archangeli & Pulleyblank 2007; Gafos & Dye 2011; Rose & Walker 2011; Finley 2017). Consider the Turkish pattern of backness harmony, where suffix vowels take on the backness value of the rightmost vowel in the base (Clements & Sezer 1982; Nevins 2010). Consonants do not participate and are ‘skipped over’ when determining appropriate suffix allomorphs.7 Data for the pattern are provided in (8), where the plural suffix alternates between front [-ler] and back [-lar] and the genitive suffix alternates between front [-in] and back [-ɯn].

An OTSL₂ transducer for this process is depicted in Figure 7. The tier for this function is all and only the output vowels, though for reasons of space, the transducer collapses all the front vowel states and the all back vowel states together. The transitions are also collapsed such that a transition labelled ‘[αbk]:[βbk]’ means that an input vowel specified as [αback] gets mapped to its [βback] equivalent (with all other features unchanged). Turkish allows disharmonic bases, and some suffixes do not alternate, instead remaining faithful and starting a new domain of harmony, so we assume that harmony can only affect segments with missing backness values, marking under-specification as [0bk].8 The transducer models the intuition that a vowel underspecified for [±back] will take on the [±back] value of the closest specified vowel to its left. Consonant transparency is captured in this transducer by the fact that reading and producing a consonant never causes a change of state.

The transparency of consonantal segments in vowel harmony is a matter of some debate. Some researchers adopt a “local spreading” approach where the harmonic feature spreads onto and through consonants via coarticulation, (e.g., Ní Chiosáin & Padgett 2001; Jurgec 2011) rather than skipping them. Transparent segments would then be those for which the harmonizing feature does not carry any perceptual or contrastive force. Support for this idea comes from research on the reportedly transparent vowels of Hungarian. Like Turkish, Hungarian has backness harmony, although the non-low front vowels [i] and [e] are unaffected by the harmony and neither trigger nor block it (Gafos & Dye 2011). Phonetic studies reveal, however, that instances of [i] and [e] between two back vowels are produced slightly back, albeit to a sub-phonemic and likely imperceptible level (Benus et al. 2004; Gafos & Benus 2006; Benus & Gafos 2007).

Some other harmony processes, however, are not fully amenable to a spreading analysis. For example, the usual [d] of the perfective suffix /-idi/ in Yaka becomes nasal if there is a nasal obstruent in the root (Hyman 1995; Walker 2000; Rose & Walker 2004; 2011; Archangeli & Pulleyblank 2007; Jurgec 2011). The root in (9a) contains no nasal consonant, so the suffix surfaces faithfully. Compare this to the roots in (9b–c) which do have a nasal consonant. No matter whether this nasal consonant is in the adjacent syllable (9b) or several syllables away (9c), it forces the suffix to harmonize and surface as [-ini]. This harmony for the feature [±nasal] occurs across vowels and voiceless obstruents without nasalizing them to any extent (Rose & Walker 2004). We must instead allow nasality to skip over them, which we can do by excluding them from an appropriate OTSL function’s tier.

Transparency in the Yaka pattern is no more or less difficult to describe using a TSL function than transparency in Turkish or Hungarian vowel harmony. This is because the TSL class places no limits on which collections of segments can act as a tier. As we mentioned earlier in Section 4, the TSL functions are agnostic as to why the tier takes a particular shape. We believe that it is good practice to try and define tiers relative to a feature theory, but also believe that the possibility of arbitrary tiers is advantageous since it is not always possible to derive a segment’s tier membership from external factors (e.g., the shape of the phoneme inventory). For example, the low vowel /a/ undergoes tongue root harmony in Kinande (Cole & Kisseberth 1994; Gick et al. 2006) while it resists and blocks tongue root harmony in Pulaar (Archangeli & Pulleyblank 1994), even though there are no relevant differences between the languages that can explain this discrepancy (Rose & Walker 2011).

Another behaviour that has received plenty of attention in the phonological literature is so-called parasitic harmony, where the source and target interact on one dimension only when they agree along another. The most prominent cases of parasitic harmony involve rounding harmony depending on vowel height. Take for instance the Kachin dialect of Khakass. Suffix high vowels in this language become round if the nearest leftward vowel is also high (Korn 1969; Kaun 1995). The data in (10) show a [+high] suffix vowel harmonizing with [+high] vowels (a and b) but failing to harmonize with [–high] vowels (c and d). As the additional data in (11) show, a [–high] suffix vowel never harmonizes, even if the preceding vowel is also [–high].

Let us consider how the OTSL₂ transducer in Figure 8 models the pattern. The tier includes all vowels, so the machine is always in the state corresponding to the most recently produced vowel. For readability, the two [+high, +round] states are collapsed together, as are the states for the six remaining vowels. While in a [+high, +round] state (i.e., the [y] or [u] state), reading /i/ will produce [y] and reading /ɯ/ will produce [u]. The same vowels are produced faithfully while in any other state. By coordinating the work of the tier and the work of the transitions, we can ensure that (i) only high vowels are ever affected by vowel harmony and (ii) they are only so affected when the preceding vowel is also high.

Rounding harmony in Khalkha Mongolian is very similar to rounding harmony in Kachin Khakass but also exhibits blocking effects. As in Kachin Khakass, rounding harmony is parasitic on height, in this case requiring the target and trigger to both be non-high (Svantesson et al. 2005; Nevins 2010; Gafos & Dye 2011). The harmony causes alternations in a variety of suffixes, such as the comitative, data for which are shown in (12).

Note that there is a simultaneous process of advanced tongue root (ATR) harmony; our analysis abstracts away from this additional process. The high front vowel /i/ is transparent to rounding harmony (Nevins 2010): it does not become rounded when preceded by a round vowel of any height, but also does not prevent rounding from reaching a following [–high] vowel. This is shown in (13) using words with the accusative and reflexive suffixes.

The other high vowels /u/ and /ʊ/, however, do prevent rounding from reaching a following [–high] vowel, as can be seen from the words in (14) where the causative suffix comes between a root and the perfective suffix.

Blocking is handled straightforwardly in TSL functions by including blockers on the tier. For example, the Khalkha pattern can be modelled by the OTSL₂ transducer in Figure 9 whose tier contains all and only the rounded vowels. To keep the transducer legible we abstract away from distinctions along the ATR and length dimensions (e.g., the distinction between [o] and [ɔː]) and ignore the parallel process of ATR harmony. The vowel [o] is included on the tier because it triggers rounding harmony and the vowel [u] is included because it blocks rounding harmony. The vowels [i] and [e] (as well as consonants) are excluded from the tier because they neither trigger nor block rounding harmony. Reading the mid vowel /e/ while in the [o] state will produce [o], no matter how many consonants or instances of [i] have been produced since the [o] that put us in the [o] state. If at any point we produce a blocker [u], we move to the [u] state, out of which all transitions are faithful. Rounding harmony can only apply again if a new instance of [o] is produced.

Segmental blocking effects are not limited to vowel harmony. Although rare, a few cases of long-distance consonantal phenomena exhibit blocking effects. These include sibilant harmony in Slovenian (Jurgec 2011), sibilant harmony in Kinyarwanda (Walker & Mpiranya 2006; Walker et al. 2008), sibilant harmony in Imdlawn Tashlhiyt (Elmedlaoui 1995; Hansson 2010b) and liquid dissimilation in Georgian (Fallon 1993; Odden 1994). Blocking can also be morphologically or lexically driven. We mentioned earlier in Section 5.1 that some suffix vowels in Turkish are invariant, like the vowel in the nominalizer suffix /-gen/ which is always [–back] (Nevins 2010: pp. 33–34). The /e/ in /-gen/ acts as a blocker in the sense that it stops the spread of [+back] by remaining [–back], but differs from the cases of blocking above by actively causing all following vowels to take on [–back]. As we showed, one way of ensuring this kind of behaviour in a TSL function is to make a distinction between input vowels unspecified for some feature and input vowels pre-specified for the same feature; the former will take on a value for the empty feature based on the most recent tier element (i.e., based on the current state), but the latter will maintain the specification that they already have.

The last type of segment we discuss from the TSL perspective is what Jurgec (2011) calls an icy target. These segments act much like a blocker in that they prevent harmony beyond themselves, but differ from blockers in that they undergo the harmony that they block. An instance of iciness comes from the Macro-Jê language Karajá, which has a regressive ATR harmony process that spreads [+ATR] (Ribeiro 2003; Rose & Walker 2011; Walker 2012). Underlyingly [–ATR] high vowels are the icy targets: an underlying [+high, +ATR] vowel will trigger harmony, while an underlying [+high, –ATR] vowel will undergo harmony but then block its spread (Ribeiro 2003). In other words, derived [+high, +ATR] vowels cause harmony to halt. Compare the examples in (15a–b), in which harmony spreads throughout the word, with those in (15c–d), which contain icy targets.

Our analysis abstracts away from the local nasal displacement that derives [-ni] from /-dĩ/; it is challenging to implement multiple processes with a single TSL function, but see Section 6.1 for extensions to the TSL class designed with this issue in mind. The pattern is sensitive to the [±ATR] value that each vowel has in the input string and so an ITSL₂ function is required. To keep the transducer in Figure 10 legible, we use only the following subset of the Karaja vowel inventory: /i/, /I/, /u/, /ʊ/, /e/, /ε/, /o/, and /ɔ/. Limiting the inventory does not significantly affect the analysis. Because the process is regressive, the input string is read from right to left. The FST’s tier includes underlyingly [+ATR] vowels alongside /I/, /ʊ/. Crucially, /ε/ and /ɔ/ must be excluded from the tier so that reading them while in the [+ATR] state does not move us to the [–ATR] state. While it might feel odd to let non-tier elements be mapped unfaithfully, doing so does not violate the definition of an ITSL function in any way.9

Compare this to the transitions originating in the [+ATR] state for the inputs /I/ and /ʊ/ which do belong on the tier and thus do lead to the [–ATR] state. As a result, [+ATR] harmony can affect and pass over/through an underlyingly [–ATR] mid vowel, whereas it can affect but not pass over/through an underlyingly [–ATR] high vowel.

It is worth noting that, despite using an input-oriented function, we are generating what looks like iterative output-oriented application. Such “iterative” application is possible with an ITSL function when non-icy targets are off the input tier and do not prevent the trigger from remaining in memory (i.e., remaining in the state label). For another example, while we present Turkish vowel harmony as OTSL in Section 5.1, it can equally be computed by an ITSL function provided that affix vowels are underspecified and provided that underspecified vowels are off the tier. In fact, the ITSL transducer looks exactly the same as the OTSL transducer in Figure 7 aside from changing “[]” to “//” in the state labels.

All of the long-distance patterns discussed so far share one striking thing in common: they are all TSL_k for k = 2. This is not surprising when we consider the typical interpretation of long-distance processes. Long-distance harmony is usually construed as the feature value of one segment spreading in some direction to affect other eligible segments, so it makes sense that a window of length 2 is sufficient in the tier-based context, since it lets us remember the most recent “relevant” element. Long-distance dissimilation can also generally be reduced to the influence of the most recent relevant element. The prominence of k = 2 is also interesting with regards to learnability. Burness & McMullin (2019) showed that while any OTSL_k function can be learned efficiently from positive data when the tier is known in advance, only the OTSL₂ functions can be efficiently learned by their algorithm from positive data when the tier is not known in advance.10 Nonetheless, there are several behaviours that require a value of k > 2 for various reasons.

A first example is the rounding harmony in one variety of Oroqen. Some sources analyze the harmony as only being triggered by a sequence of two rounded vowels (Zhang et al. 1989; Li 1996; Zhang 1996; Zhang & Dresher 1996; Walker 2001; Walker 2014). The data in (16) show the definite article suffix becoming round when preceded by two round vowels, but not when preceded by a single round vowel (even if this vowel is long). Note that the language also contains a process of ATR harmony, hence the alternation between [ɔ] and [o]. An alternative analysis of the same data comes from Dresher & Nevins (2017), who analyze the harmony as triggered specifically by non-initial vowels. They analyze the process in this way because the Russian loanword [kinɔ] ‘film’ causes rounding harmony in the definite object suffix /-wa/ giving us [kinɔ-wɔ] instead of *[kinɔ-wa] as predicted by the double-trigger analysis (Dresher & Nevins 2017). There also exists a plural suffix /-nOr/ for kinship terms that is always round, and this suffix causes rounding harmony regardless of the rounding in preceding vowels, giving us [ǝtʃǝxǝ-nɔr-wɔ-t] ‘paternal.uncle-PL-DEF-ACC’ instead of *[ǝtʃǝxǝ-nɔr-wa-t], for example (Dresher & Nevins 2017). This again is expected under the non-initial trigger analysis, but not under the double trigger analysis.

Interestingly, both the double trigger analysis and non-initial trigger analysis can be implemented as an OTSL function if we set k to be greater than or equal to 3. The states in a TSL_k transducer are labelled with sequences of up to length k – 1. Accordingly, until enough tier elements have been encountered, the transducer can be in a state labelled with fewer than k – 1 segments, but it will cycle through states labelled with k – 1 elements once that number is reached. For example, an OTSL₃ transducer with the alphabet {V, C} and the tier {V} will enter the state ‘V’ upon producing its first vowel, and will not move to the state ‘VV’ until a second vowel is produced. After that point it will remain in the state ‘VV’, never returning to the state ‘V’. This is illustrated in Figure 11. When implementing the double-trigger analysis as an OTSL₃ function, we would ensure that rounding harmony is only enforced out of a state whose label consists of two round vowels. Similarly, when implementing the non-initial trigger analysis as an OTSL₃ function we would ensure that rounding harmony is only enforced when the state label contains two vowels and the rightmost of these is round.

Similar to how the right-hand vowel of a two-vowel state label in a progressive TSL₃ function is necessarily non-initial, a one-vowel state would necessarily reflect the first vowel when all vowels are on the tier. With k = 3, then, we can also model non-iterative harmony that is triggered specifically by the first or last vowel in a word. In Megisti Greek, regressive non-iterative backness and rounding harmony is triggered only by the last vowel in a word (van Oostendorp & Revithiadou 2005; McCollum & Kavitskaya 2018). Harmony preceding a final back vowel is shown in (17a) and harmony before a final front vowel is shown in (17b). The example in (17c) shows that the harmony does not extend past the penultimate vowel.

Trigger status is purely positional in this pattern and has nothing to do with stress placement (McCollum & Kavitskaya 2018), so we cannot rely on a dichotomy between stressed and unstressed vowels to derive the restriction on triggers. A TSL analysis of this pattern (or its mirror image) needs a tier of all vowels and k = 3. A state labelled with a single vowel will then correspond to having seen only the first vowel in a left-to-right machine and correspond to having only seen the last vowel in a right-to-left machine. Restricting harmonic transitions so that they can only come from these states will limit triggers to the desired word edge.

Values of k higher than 2 can thus account for certain behaviours not captured by the TSL₂ functions, such as double triggering and some instances of positional triggering. Not all instances of positional triggering, however, can be analyzed in the way outlined above. For example, suffixes in the Eastern Meadow dialect of Mari harmonize with the initial vowel in backness across all other vowels (Vaysman 2009; Walker 2011).11 This particular process cannot be modelled by inflating k since it is iterative and there is no way to exclude non-initial vowels from the tier by identity alone, so the initial vowel will eventually be pushed out of the memory window (i.e., the state label of the FST). We conjecture that positional triggering of this kind requires something like the structure-sensitive tier projection methods explored for formal languages by Graf & Mayer (2018), Mayer & Major (2018), and De Santo & Graf (2019), which consider surrounding material in addition to segment identity.

The Tamashek dialect of Tuareg contains a process of long-distance regressive sibilant harmony and a process of long-distance regressive labial dissimilation (Heath 2005; McMullin 2016). The sibilant harmony can be seen in words where the causative prefix /s-/ is followed non-locally by another sibilant, whereupon it takes that other sibilant’s values for anteriority, voicing, and pharyngealization as shown by the data in (18) from Heath (2005: p. 442). Note that the language has considerable vowel allophony, and we write ‘V’ where Heath (2005) does not provide the surface vowel quality.

The labial dissimilation can be seen in words where a prefix /m/ (such as in the mediopassive) is followed non-locally by a labial consonant other than /w/, whereupon the prefix /m/ will dissimilate to [n]. Data for this process is shown in (19) from Heath (2005: p. 472).

That both processes can occur simultaneously is demonstrated by the word in (20) from Heath (2005: p. 462), which contains the causative and mediopassive prefixes together.

The combination of sibilant harmony and labial dissimilation cannot, however, be computed by a single TSL function. Consider what happens when we try with an OTSL₂ function whose tier consists of all sibilants and labial consonants. Producing a sibilant will push the most recent labial consonant (if any) out of the k – 1 window, and producing a labial consonant will push the most recent sibilant (if any) out of the k – 1 window. At any given point, then, we can only know how to correctly map an input /s/ or only know how to correctly map an input /m/, but not both. Increasing k does not eliminate the issue, since any number of sibilants/labials can in principle occur between two labial/sibilant consonants.

A further difficulty for TSL functions posed by Tamashek Tuareg is that long-distance regressive labial dissimilation is overridden by a local process of regressive nasal place assimilation. An input /m/ fails to dissimilate specifically when it is immediately followed by an oral labial stop, in order to avoid a heterorganic cluster. This can be seen in a word like (21) from Heath (2005: p. 476) where the reciprocal prefix /Vm-/ comes immediately before a /b/.

We are faced with a paradox if we attempt to model this interaction as a single TSL function. In order to know when an input labial needs to dissimilate we need to ignore everything that is not a labial consonant, but in order to know when an input labial needs to obey place assimilation we cannot ignore anything.

Whether such interactions between multiple local and/or long-distance processes are problematic for using TSL functions as a model of long-distance phonology depends on whether we are trying to study properties of individual processes/maps or properties of entire phonological systems. The latter perspective is explored by Chandlee & Heinz (2018) and Chandlee et al. (2018) in the context of formal language theory and automata theory. In an appendix to their article, Chandlee et al. (2018) prove that the ISL functions are not closed under composition (i.e., given two ISL functions f(w) and g(w), the single function equivalent to f(g(w)) is not guaranteed to be ISL),12 and yet the main body of their article shows that certain opaque rule interactions such as counterfeeding and counterbleeding can nevertheless be modelled using a single ISL function, suggesting that overall phonological systems might generally obey strict locality. In a similar vein, preliminary work by Burness & McMullin (2020) explores how to combine multiple TSL functions into a single function based on insights from research by Aksënova & Deskmukh (2018) and McMullin et al. (2019) into phonotactic patterns that operate over multiple tiers. The particular subclass of multi-tiered functions that Burness & McMullin (2020) argue for lets each input element separately depend on its own set of tiers, provided that the set forms a strict superset-subset hierarchy. Further work is needed, however, to assess the degree to which tier-based strict locality is obeyed by phonological systems overall. On this note, a reviewer observes that the interaction between dissimilation and assimilation in Tamashek Tuareg is similar to a minimum distance requirement, suggesting that tier-based computation may avoid certain pathologies only at the level of an individual process.

One aspect of long-distance patterns is tacitly assumed above, namely that they tend to apply in a single direction. This seems to be the norm, but there are patterns that apply in both directions, typically from the root outwards. Take for instance vowel harmony in Degema, where prefixes and suffixes take on the [±ATR] specification of the root (Archangeli & Pulleyblank 2007; Kari 2007). The data in (22) show both parts of a circumfix alternating to match the root’s value for [±ATR]. The combination of regressive harmony to prefixes and progressive harmony to suffixes gives the impression of a harmony system that begins from the centre. TSL functions obligatorily start at either the left or right edge of the input, so even if we make a distinction between root and affix vowels by having the latter be unspecified for [±ATR] in the input, we will only correctly treat either the prefixes or the suffixes.

A deceptively simple solution presents itself: why not apply the same TSL function once going from left to right, then a second time going from right to left? The first pass will fill in the missing [±ATR] value on suffixes and the second pass will fill in the missing [±ATR] values for prefixes. A similar idea of decomposing a single bidirectional process into an ordered pair of opposite-direction subsequential functions is how Heinz & Lai (2013) account for stem-controlled vowel harmony, though they caution against freely composing subsequential functions due to a theorem from Elgot & Mezei (1965). The theorem states that running a first subsequential transducer in one direction and then a second subsequential transducer in the reverse direction can describe any regular function. This happens because the first transducer can “annotate” the input string to give the opposite-direction transducer information about distant upcoming material. Heinz & Lai (2013) accordingly suggest that when we need to split a single process into two parts, the first transducer’s output alphabet must be equal to its input alphabet (which is then the input alphabet to the second transducer), and must not be allowed to produce an output longer than the input. These restrictions prevent some of the annotation necessary for producing truly regular functions, and functions describable in this manner are known as the weakly deterministic functions. Since we argue that the TSL functions are a more natural model of long-distance phonology than the subsequential functions, it would be interesting to see whether we can model bidirectional processes as a pair of opposite-direction TSL functions without the use of intermediate encoding.13 We leave a thorough investigation of this possibility for future research.

ISL functions are able to model two-sided contexts since they can wait up to a finite number of steps before transforming an input element. This ability is not in general available to ITSL functions, so a challenge for the TSL models is that there do exist patterns that can be interpreted as being affected by non-local information in one direction as well as bounded information in the other. Consider the lowering harmony in C’Lela, where suffix high vowels become mid if they are preceded by a non-high vowel in the root (Dettweiler 2000; Pulleyblank 2002; Archangeli & Pulleyblank 2007; Michel 2009; Jurgec 2011). When there is more than one vowel following the triggering root vowel, the harmony only affects the very last one, which will always be in word-final position thanks to the syllabic structure of C’Lela (Jurgec 2011: p. 186). The data in (23) show that the class membership suffix /-i/ will lower to [e] when it is the only suffix following a non-high root vowel, but will be unaffected when it is followed by another suffix vowel.14

The basic facts of lowering are simple enough to account for with an ITSL₂ or OTSL₂ function: the tier consists of non-high vowels, and input high vowels will be output as non-high while in a non-high state. Accounting for the fact that targets are only lowered in word-final position, on the other hand, lies outside the powers of the TSL class. In order to confirm that an input vowel is word-final, we need to postpone its output until we read the next input element: if anything except the word boundary follows, it is not word-final. A paradox ensues: the lowering requires a tier with only non-high vowels, while determining whether the vowel is word-final requires a tier with everything. The multi-tiered functions of Burness & McMullin (2020) seem well-suited to resolving this paradox, since a local tier is by necessity a strict superset of any tier used to keep track of non-local information. Another possibility, as suggested by a reviewer, would be to appeal to structure-sensitive tier projection (Graf & Mayer 2018; Mayer & Major 2018; De Santo & Graf 2019)

Related to hybrid local/non-local cases like C’Lela lowering harmony is what Jardine (2016) calls unbounded circumambience, where the application of a process depends on potentially non-local information in both directions simultaneously. Take for instance Tutrugbu vowel harmony, as analyzed by McCollum & Essegbey (2018) and McCollum et al. (2020). Root vowels that are [+ATR] spread this value leftwards to prefix vowels, and when all prefix vowels are of the same height, the harmony will reach the left word edge (McCollum & Essegbey 2018; McCollum et al. 2020), as seen in (24a) for a string of [+high] prefixes and (24b) for a string of [–high] prefixes. Roots are underlined for clarity, and tone is not indicated to keep [I] and [i] visually distinct.

The behaviour of strings of prefixes with different heights depends on the height of the leftmost vowel. Harmony spreads to all prefix vowels when the leftmost vowel is [–high] as seen in (24c), but harmony is blocked by [–high] vowels when the leftmost vowel is [+high] as seen in (24d), although harmony still spreads up until that [–high] blocker (McCollum & Essegbey 2018; McCollum et al. 2020). The outcome of an input [–high] vowel can therefore depend simultaneously on non-local information to its left (the height of the leftmost vowel) and non-local information to its right (the ATR specification of the root), creating clear instances of unbounded circumambience. Jardine (2016) hypothesized that unbounded circumambient processes were not weakly deterministic according to Heinz & Lai’s (2013) definition, although O’Hara & Smith (2019), Smith & O’Hara (2019), and Lamont et al. (2019) show that loopholes in the definition can be exploited to model several unbounded circumambient patterns.15 We similarly conjecture that cases of unbounded circumambience like the one in Tutrugbu could be modeled as a pair of opposite-direction single-tiered or multi-tiered functions without the need for abstract intermediate encoding, although we leave to future research the task of determining the limits on such composition that would prevent the modelling of fully regular processes.