2.1 Intensional and extensional descriptions

It will be helpful to make clear a distinction between grammars, on the one hand, and the objects grammars describe, on the other. Grammars are intensional descriptions of objects, and the objects themselves are extensional. The objects may be infinite in size, but the intensional descriptions must be finite. These distinctions are common in mathematics. Lines on a Cartesian plane are sets of infinitely many points, and have many intensional descriptions. For example, they can be described with an equation of finite size of the form y = ax+b; they can also be described with any two distinct points on the line, such as (x, y) and (x ′, y ′). However the equations and points are not the lines themselves, but descriptions of them. They are intensional descriptions (grammars), while the infinite set of points is the extension of these descriptions. While these are familiar concepts in mathematics, and perhaps hardly worth mentioning, it is important to keep this distinction in the forefront of one's mind when thinking about grammars, since the distinction is equally valid. What is the extension that a grammar describes?

To make the point concrete in phonology, consider a language where word-final vowels delete. There are different grammars which can describe this fact. One could formulate the SPE-style rewrite rule shown in (1a), while in an OT grammar one might (in part) employ the ranking shown in (1b).

1. (1)

   

What are the extensions of these grammars? We argue that, like lines on Cartesian planes, the extension can be understood as an infinite set of points, with the left coordinate being the input form and the right coordinate being the output form. This infinite set of points includes pairs like (kapa, kap), (tiki, tik) and (plabo, plab). We assume this extension also includes points like (rek, rek), (malarakalark, malarakalark) and (b, b). This is consonant with the principle of the rich base (Prince & Smolensky 1993) and with the assumption that a rule's output is identical to its input when it fails to apply. We can now ask what kind of set of points this is. More specifically, what computational properties explain the nature of the sets of points that represent phonological maps? In the next section we define one such property: Input Strict Locality.

2.2 Input Strictly Local functions

We will first define ISL functions through a metaphor, and then provide a more precise, formal characterisation. First, the metaphor. You are a computer asked to return the surface representation y of some underlying representation x. You begin this process by reading from the beginning of x and moving through the string left to right. As you read x, and perhaps before you finish reading x, you begin writing the output y also from left to right. The key idea behind Input Strictly Local functions is this: there is some positive integer k, such that what you write at any given point in this process only depends on the last k symbols you read in x. Figure 1 illustrates this point, with k = 2.

Figure 1

A schematic illustrating the Markovian nature of Input Strictly k-Local functions. For every Input Strictly 2-Local function, the output string y _i of each input element x _i depends only on x _i and x _i−1. In other words, the light grey cell depends only on the dark grey cells.

The metaphor of reading and writing from left to right and paying attention to only the most recent k symbols in the input is useful, but inaccurate in one important way. As it turns out, it does not matter if the string is read left to right or right to left. All that matters is that if the input x is n symbols long (so x = x ₁x ₂ … x _n, with each x _i a letter), we can think of the output y as the concatenation of n strings (so y = y ₁y ₂ … y _n, with each y _i a string), where each y _i only depends on the string x _i−k+1 … x _i (which is of length k). The order in which each y _i is computed does not really matter.

One might think that ISL functions can only describe surface representations which are at least as long as the underlying representations they are computed from, because there are n-many y _i strings. However, we should not forget that y _i can also be the empty string, the unique string of length zero (which we denote λ). Not only does this make ISL functions able to model deletion processes, it also allows them to describe phonological processes with both left and right contexts. Examples like this are provided in the following section and throughout §3.

2.3 Finite-state characterisation of ISL functions

ISL functions have been characterised in terms of automata theory, formal language theory (Chandlee Reference Chandlee2014, Chandlee et al. Reference Chandlee, Eyraud and Heinz2014) and first order logic (Chandlee & Lindell Reference Chandlee, Lindell and Heinzto appear). Here we provide a finite-state transducer (FST) characterisation. This characterisation is derived from the original definition, which is provided in Appendix A.Footnote ³

What is a FST? Figure 2 shows a FST for the example of word-final deletion discussed earlier. A FST includes a finite set of states (shown as circles), with one state being designated the start state (the one with the unlabelled incoming arrow) and some set of states designated as final states (circles with double perimeters). It also includes a set of transitions between states that determine (i) how the state changes when reading some input letter, and (ii) what output is written; transitions are shown as arrows between states with the label a:w, meaning letter a is read and string w is written.

Figure 2 is a FST whose extension is a map for word-final vowel deletion. An input x is mapped to an output y only if there is a path from state 1 (the start state) to state 2 (in this FST the only final state) which reads a sequence corresponding to x and writes a sequence corresponding to y. In this FST, C and V serve as variables such that any input segment in the class of consonants or vowels can follow a transition marked C or V.

Figure 2

FST for word-final vowel deletion.

For example, the input string /CVC/ is mapped to [CVC] because the path in (2a) is a valid path in the FST (i.e. starts in the start state and ends in a final state). (2b) is a path which computes the output of /CVCV/.

1. (2)

   

Note that any path which ends in state 1 is not valid. Also, note that an input like /CVV/ will map to [CV], so only one final vowel is deleted. Thus this map is identical to the extension of the SPE-style rule in (1a) applying simultaneously, and it is not identical to the extension of the OT grammar in (1b), which deletes all final vowels. To make a FST which deletes all final vowels one would have to add a transition from state 2 to itself with the label V:λ. This FST would now match the extension of the OT grammar in (1b), as well as the extension of the SPE-style rule in (1a) applying right to left or persistently.

One kind of FST is necessary and sufficient to describe ISL functions. Figure 3 shows an ISL FST with the same extension as the FST in Fig. 2. Recall that a map is ISL if there is a positive integer k such that the ith part of the output string depends only on the last k letters up to and including the ith symbol read. In a FST, this is encoded in the states: basically, each state corresponds to the last k−1 letters read in the input, which means there must be a state for each k−1 sequence of input that could be read.Footnote ⁴ This in turn means the ISL FST will have more states than the non-ISL version, so for readability the FST in Fig. 3 assumes a reduced alphabet with one consonant and one vowel: {t, a}.Footnote ⁵

Figure 3

The ISL FST for word-final vowel deletion.

Instead of indexing states with numbers as we did in Fig. 2, it makes sense to label states with the sequence they correspond to. Another difference in Fig. 3 is that both the input and the output strings explicitly encode beginning and end markers, using the symbols ⋊ and ⋉ respectively.Footnote ⁶ In Fig. 3, k = 2, so five states are needed to keep track of possible input sequences up to length k−1 or 1. These states are λ, t, a, ⋊ and ⋉.

The transitions in an ISL FST are organised in a very simple, specific way. Basically, if the FST is in a state corresponding to the sequence t and the letter a is read, then the FST transitions to the state which corresponds to the last k−1 letters of ta. When k = 2, as in Fig. 3, this means whenever a is read, the FST transitions to state a, and whenever t is read it transitions to state t. There is only one final state (labelled ⋉), and every transition which reads the end marker ⋉ goes to this final state.

To see how this FST works, the valid paths in (3a) and (b) show the mapping of tat to tat and tata to tat respectively.

1. (3)

   

These examples illustrate how the states and the ability to write the empty string λ allow the ISL FST to deterministically decide whether to write a given vowel or not. When an a is read, it is not written out right away. This is because, at that point, as the string is processed left to right, it is unknown whether that a is word-final or not. If it is word-final, nothing further is written, and the FST moves to the final state upon reaching the end marker. If it is not, the first symbol of the next part of the output is always a.

2.4 Properties of ISL functions

ISL functions have several important properties that are important to the study of phonology. First, Chandlee (Reference Chandlee2014) and Chandlee & Heinz (Reference Chandlee and Heinz2018) discuss how all phonological processes which can be described with a rule A→B / C__D applying simultaneously are ISL functions, provided only finitely many strings match the structural description (or equivalently, provided there is a longest string in CAD). This excludes long-distance phenomena (such as consonant harmony) that involve segments interacting over an arbitrary number of intervening segments.

Second, Chandlee & Heinz also explain that ISL functions do not necessarily correspond to individual processes. Maps that include multiple phenomena (such as multiple ordered rules in rule-based grammars or many interacting constraints in OT grammars) can still be ISL functions. A precise account of which such maps are ISL and which are not is an outstanding goal. This paper makes a contribution to this goal, by showing that a variety of opaque maps are ISL.

Third, ISL functions are a proper subclass not only of the regular relations, but also of the class of subsequential functions. Regular relations are those definable with FSTs of the sort illustrated in Fig. 2. Subsequential functions are definable by deterministic FSTs (see Chandlee & Heinz Reference Chandlee, Heinz and Aronoff2016 for further discussion). Thus the ISL functions are an extremely restrictive class in terms of the kind of computations they can represent. The importance of this restriction to phonological theory will be discussed further in §2.5.

Fourth, ISL functions have a clear cognitive interpretation. Rogers et al. (Reference Rogers, Heinz, Fero, Hurst, Lambert, Wibel, Morrill and Nederhof2013) explain how different subregular classes of formal languages can be understood in terms of the different kinds of memory they require (and hence distinguish). The kind of memory needed to compute an ISL function is fleeting: it is only necessary to scan the input word w and remember the most recent substring of length k. Everything else can be thrown out. It is not necessary to compare a substring in one part of w with a substring in another part of w. Nor is it necessary to remember the number of times particular substrings occurred in w. This is how ISL functions are like the Strictly Local (SL) formal languages discussed by Rogers & Pullum (Reference Rogers and Pullum2011) and Rogers et al. (Reference Rogers, Heinz, Fero, Hurst, Lambert, Wibel, Morrill and Nederhof2013). Cognitively, this is one of the simplest forms of memory.

Fifth, k-ISL functions are provably learnable by algorithms that are very efficient in both time and data (Chandlee Reference Chandlee2014, Jardine et al. Reference Jardine, Chandlee, Eyraud, Heinz, Clark, Kanazawa and Yoshinaka2014, Chandlee, Jardine & Heinz Reference Chandlee, Eyraud, Heinz, Kuhlmann, Kanazawa and Kobele2015). This means that, given any k-ISL function f and a sufficient finite set of points exemplifying f, these algorithms invariably return a FST whose extension is f. Furthermore, the time the algorithm takes is reasonable with respect to the size of its input data. Additionally, the amount of data needed is also reasonable with respect to the size of the ISL FST corresponding to f. Here, ‘reasonable’ has a clear meaning from the theory of computational complexity; the abovementioned papers provide the details. These results are significant, because comparable results do not exist for the subsequential class nor for the class of regular relations. While a learning algorithm exists for the subsequential class (Oncina et al. Reference Oncina, García and Vidal1993), it is less efficient than the algorithms for k-ISL. And, provably, no algorithm exists which exactly identifies the class of regular relations from positive data.

2.5 Relevance to phonological theory

Above it was stated that the ISL functions are a restrictive class of maps – they are subclasses of both the subsequential and regular classes of maps. To better situate the results presented in the next section, we first comment here on why this is important for phonological theory, and where other phonological theories lie in terms of the maps that they can describe.

Those unfamiliar with formal language theory might wonder why restrictiveness matters, but an analogy with OT will hopefully help make the relevance clear. Suppose there were three competing sets of constraints under typological investigation (call them Con₁, Con₂ and Con₃). If it became known that the typology of Con₃ was properly included in Con₂, which was in turn properly included in Con₁, this would be a fact worth knowing. It would tell us that any map describable with Con₃ is describable with Con₂ and Con₁, but not vice versa.

Likewise with these classes of maps. Every ISL function is subsequential and regular, but not vice versa. This means ISL functions are restrictive in a computationally important way, and so an ISL theory of phonology draws a small circle around a large class of phonological maps. Such maps are indeed also regular (as shown by Johnson Reference Johnson1972 and Kaplan & Kay Reference Kaplan and Kay1994), but the ‘ISL circle’ is a tighter, and therefore stronger, characterisation. Importantly, this is a better characterisation – in computational terms – than characterisations in OT and SPE. SPE rules describe the entirety of the regular maps (Johnson Reference Johnson1972, Kaplan & Kay Reference Kaplan and Kay1994), and OT can describe maps outside of the regular class (Frank & Satta Reference Frank and Satta1998, Riggle Reference Riggle2004, Gerdemann & Hulden Reference Gerdemann and Hulden2012).

It is often pointed out that SPE rules or OT grammars more easily capture the distinction between ‘natural’ and ‘unnatural’ processes, and therefore provide better typological predictions than computational restrictions. However, ‘naturalness’, in common practice, is implemented as a metatheoretic restriction based on phonetic principles on possible rules or constraints, and their interactions or rankings (as in the papers in Hayes et al. Reference Hayes, Kirchner and Steriade2004). We argue that these same types of restrictions could also be used to further restrict the class of ISL functions to a class that is both computationally appealing and phonetically natural. However, since the focus of the current paper is to characterise the computational nature of opaque maps, we do not attempt to do so here.

To summarise, subregular function classes like ISL present a learnable, restrictive, computational theory of phonological maps. The next section explores the kinds of opaque maps ISL functions are capable of describing, using Baković (Reference Baković2007) and Kavitskaya & Staroverov (Reference Kavitskaya and Staroverov2010) as a catalogue of the known typology of opaque maps. These works were chosen because they provide a more comprehensive collection of opaque phenomena that go beyond the classic examples of counterbleeding and counterfeeding (Kiparsky Reference Kiparsky and Dingwall1971, Reference Kiparsky and Fujimura1973). Despite the nuanced differences among the types of opaque maps we will analyse, the fact is that all have the ISL property.

3.1 Input/output tables

The example ISL FST in §2 (Fig. 3) has a simple alphabet of two letters (t and a). To describe the phonology of a language at the level of its phonemic and phonetic inventory, it will be necessary to have symbols for each element of these inventories. Consequently, the number of states and transitions will increase dramatically, making the FST harder to read in graphical form. Generally, if there are n letters in the alphabet, the number of states in a k-ISL FST is n ^k+1, because there are n ^k−1 states corresponding to the sequences up to length k−1 plus the ⋊ and ⋉ states.

While the size of ISL FSTs may seem daunting, keep in mind that these are not the smallest FSTs with these extensions. There are efficient procedures which can make them much more compact (Mohri Reference Mohri1997). The size of ISL FSTs follows from their particular structure, which is designed to make clear that the functions they compute are ISL.

What we are calling an input/output table is basically a list of the transitions of the ISL FST. A full input/output table for the ISL FST in Fig. 3 which models word-final vowel deletion is shown in Table I. The rows in an input/output table serve the same purpose as the transitions of a FST: the current output is determined by the current (k−1)-suffix (the sequence of k−1 previous symbols) and the current input symbol. Recall that for the function depicted in Fig. 3, k = 2, so Table I lists 1-suffixes. For example, row (g) indicates that an a following a t should be output as λ. Because of the particular structure of ISL FSTs, the destination state of this transition can be inferred: it is the last k−1 symbols of the 1-suffix concatenated to the new input. In this example, that would be the last k−1, or 1, symbols of ta, so the FST would proceed to state a.

Table I

Full input/output table for the ISL FST in Fig. 3.

The process of mapping an input string to its output string can be thought of as sliding a window of length k over the input from left to right. This window is moved one input symbol at a time, not unlike a FST. This process is demonstrated in (5) with the derivation /tat/ → [tat]. The left portion of the window reveals the current (k−1)-suffix (again in this example, it is a 1-suffix, since k = 2). The right portion of the window includes the current input symbol. For each new input symbol, we look up its corresponding output given the (k−1)-suffix in the input/output table. To clarify the roles of each symbol, the shading in the derivation matches the shading in the table. Additionally, each step is labelled with its corresponding row letter from Table I. The first step, which corresponds to row (a), has been omitted.

1. (5)

   

We will make these input/output tables even more succinct, by not showing those rows where the inputs and outputs are identical. An abbreviated input/output table is one which only shows cases where the inputs do not match the outputs. Table II shows an abbreviated input/output table for the ISL FST in Fig. 3. In contrast to Table I, Table II has only three rows. In addition to improving readability, the advantage of an abbreviated input/output table is that we can isolate the ‘interesting’ part of the FST, or the part that represents the structural change of the phonological map. For any input symbol and (k−1)-suffix not found in the abbreviated input/output table, it is understood that the output written is identical to the input (as in steps (c) and (e) in (5)).

Table II

Abbreviated input/output table for the ISL FST in Fig. 3.

To illustrate the kind of analysis we will conduct in this paper, consider a classic case of counterfeeding opacity: vowel lowering in Danish (Lundskaer-Nielsen & Holmes Reference Lundskaer-Nielsen and Holmes2011). In Danish, front vowels lower in proximity to /r/. This occurs in a chain shift, in which each vowel lowers to the vowel one ‘step’ in height below it. To simplify the discussion, we focus on front vowels following /r/. A simple rule-based analysis is presented in (6), with the rules applying in the order presented.

1. (6)

   

This lowering process is a 2-ISL function: whether or not an input /i/ is output faithfully depends on whether or not the preceding segment in the input is an /r/. We can describe this function exactly with the abbreviated input/output table in Table III.

Table III

Abbreviated input/output table for lowering in Danish.

An example derivation is given in (7).

1. (7)

   

Table III succinctly represents the map which lowers front vowels after /r/. We use such tables throughout this paper to show that opaque interactions of ISL phonological maps are themselves ISL – that is, for these interactions, there exists some k such that the relevant changes from input to output are determined by (k−1)-suffixes in the input.Footnote ⁹ To make the tables more compact and readable, we will use symbols like C, N and V as variables in the conventional manner, though in the actual FSTs each segment would again be represented separately.

3.2 Cross-derivational feeding in Lithuanian

We begin with an interaction between epenthesis and voicing assimilation in Lithuanian that is 2-ISL. Baković (Reference Baković2007) identifies this as an example of what he calls cross-derivational feeding, a type of opacity in which one process applies in order to avoid a derivation in which another process would create a marked structure.

In Lithuanian, [i]-epenthesis occurs between identical obstruents and voiceless obstruents assimilate to following voiced obstruents. In (8), D represents a voiced obstruent and K any obstruent, regardless of voicing.Footnote ¹⁰

1. (8)

   

In Odden (Reference Odden2005)’s formulation, epenthesis occurs only between homorganic obstruents, but Baković (Reference Baković2007: 235) argues against this analysis, because it misses the generalisation that assimilation ‘is bled in precisely those contexts where it would otherwise create pairs of completely adjacent consonants’. He instead suggests the version shown in (8a), though with either version of the rule the interaction of epenthesis followed by assimilation is not actually opaque, but a standard case of bleeding.

Opacity comes into play when we address the fact that these two rules cannot account for the example in (9), under either ordering.

1. (9)

   

The application of epenthesis and not assimilation to /ap-berti/ is a case of overapplication. Baković calls this cross-derivational feeding because the epenthesis appears to take place in order to avoid a derivation in which voicing assimilation would create the marked structure of identical obstruents. Though this is missed by the rule-based analysis, Baković shows that it can be handled rather straightforwardly in OT. As mentioned above, our analyses do not depend on the rule-based descriptions or on the ability to decompose the generalisation into multiple individual ones. Therefore, while not considered opaque in the rule-based analysis, we include this case in our survey because its extension (which is identical in both Odden's and Baković’s analyses) reflects the type of opacity called cross-derivational feeding.

We now show that this interaction of epenthesis and assimilation can be modelled with a single 2-ISL map. The essence of this map's computation is the following. When a voiceless obstruent appears in the input, its output is temporarily delayed, until it can be determined whether or not it will be subject to voicing assimilation in (8b). This depends on the following segment. If the following segment is a voiced obstruent of a di fferent place, the voiceless obstruent should be output as voiced, because epenthesis will not be triggered. If the following segment is an obstruent of the same place, then both the voiceless obstruent and [i] are output.

This interaction is 2-ISL, because a scanning window of size 2 is sufficient to distinguish the above conditions. Table IV illustrates these various conditions. First, voiceless obstruents, which may or may not be subject to assimilation, are initially output as λ (rows (a, b, e, f)). Voiced obstruents, on the other hand, are always output unchanged (rows (c, d, g, h)).

Table IV

Abbreviated input/output table for cross-derivational feeding in Lithuanian.

When a voiceless obstruent is followed by a vowel (rows (i, m)), the end of the word (rows (j, n)) or a heterorganic voiceless obstruent (rows (k, o)), the voiceless obstruent is output faithfully. (In the latter case, the following heterorganic voiceless obstruent is not included in the output, as it may itself be subject to assimilation, depending on what comes next, per the discussion above.) If the following symbol is a heterorganic voiced obstruent, the preceding voiceless obstruent is output as voiced (rows (l, p)). The remaining cases of interest are when a voiceless obstruent precedes a homorganic obstruent. These are the cases in which epenthesis applies. When a voiceless obstruent is followed by an identical voiceless obstruent (rows (q, s)), the first obstruent is output followed by an [i]; thus for example, in (q) a /tt/ sequence is output as [ti]. In this case, the output of the second voiceless obstruent is withheld, as it itself may be followed by a trigger for voicing assimilation. When a voiceless obstruent is followed by a homorganic voiced obstruent, the voiceless obstruent is output followed by an epenthesised [i] and the voiced obstruent; thus in (r) an input /td/ sequence is output as [tid].

This final case is exactly the case of overapplication of epenthesis due to cross-derivational feeding. The preceding tables have shown this interaction to be definable by the 1-suffix of each input; thus it is 2-ISL. (10) illustrates how the correct outputs for the three crucial cases – epenthesis of identical segments, voicing in heterorganic segments and cross-derivationally fed epenthesis between homorganic segments differing in voicing – are obtained by a scanning window of size 2 implementing the input/output relations listed in the tables above. The row letters are from Table IV.

1. (10)

   

3.3 Counterbleeding in Yowlumne

We now turn to a case of counterbleeding, from Yowlumne, and show that it is 3-ISL.Footnote ¹¹ In Yowlumne, all long vowels become [―high], and vowels in closed syllables shorten, as shown in (11).

1. (11)

   

With long vowels in closed syllables, the application of shortening obscures the environment for lowering. The example in (12), from McCarthy (Reference McCarthy1999), shows apparent overapplication of (11a), because the subsequent application of (11b) removes the triggering long vowel.

1. (12)

   

These processes can be viewed as a single map, whose computation can be summarised as follows: when a high long vowel is read, the output is temporarily delayed, until it can be determined whether (i) to both lower and shorten the vowel or (ii) just lower it. Condition (i) holds if the two segments after the vowel are /C⋉/ or /CC/, where /C/ ranges over all consonants. Condition (ii) holds if the next two segments are anything except /C⋉/ or /CC/.

This map is 3-ISL, because these conditions can be checked by scanning a three-segment window in the input.Footnote ¹² (Note that /iː/ counts as one symbol.) The following abbreviated input/output tables, focusing on the lowering and/or shortening of an input /iː/, illustrate this. We assume the alphabet {iː, V, C}, where /iː/ represents long high vowels, and /C/ and /V/ are variables ranging over the set of consonants and the set of short vowels plus long non-high vowels respectively.

First, any input /iː/ will be initially output as λ, temporarily delaying its corresponding output – whether it is eventually output as [eː] or [e] depends on whether the following input is /C⋉/, /CC/ or something else. Thus its corresponding output is λ, regardless of the 2-suffix, as Table V illustrates with example rows for the input /iː/.

Table V

Abbreviated input/output table for counterbleeding in Yowlumne.

The change, then, hinges on inputs following an /iː/. If an /iː/ is followed by anything other than a /C/, it is not in the shortening environment. Thus, it can be output as [eː], with only lowering applying. Rows (i–k) in Table V illustrate this: a /V/ immediately following a /iː/ will be output as [eːV]. However, if /iː/ is followed by a /C/ (rows (l–n)), the output still cannot be determined: if it is a word-final /iːC/ sequence or if another /C/ follows, then it should be output as [eC], with both lowering and shortening; otherwise, it should be output as [eːC], with only lowering. Thus, the output must be again delayed, and so a /C/ following /iː/ is always output as λ.

Thus an input /iːC/ sequence is output as λ, as whether or not it is realised as [eːC] or [eC] is contingent on what comes next. An input /V/ following an /iːC/ sequence is output as [eːCV] (row (o)). This output comprises the output [eːC] of the /iːC/ 2-suffix (which was previously withheld), concatenated to the output [V] for the new input /V/. This can be interpreted as follows: now that the /iːC/ has been seen to precede a /V/, it is clear that the /iː/ is not in the shortening environment, and so the output reflects only lowering. In contrast, as shown in rows (p) and (q), an input /C/ or /⋉/ following an input /iːC/ is output as [eCC] or [eC⋉] respectively, reflecting both lowering and shortening.

Lastly, rows (r–y) demonstrate the application of shortening without lowering. The output for /Vː/ (which abbreviates all non-high long vowels) is [V] in the same contexts that /iː/ is shortened (i.e. closed syllables).

(13) presents the derivations /CiːCV/ → [CeːCV] and /CiːC/ → [CeC], to show how the input–output correspondences in these tables correctly capture the opaque interaction. Row letters are from Table V.

1. (13)

   

These derivations highlight the fact that a scanning window of size 3 is sufficient to model the combined shortening and lowering map – the longest (k−1)-suffix needed to produce the correct output for any input symbol is /iːC/, which is of length 2. Thus this opaque interaction is 3-ISL.

3.4 Non-gratuitous feeding in Classical Arabic

Another type of opacity discussed by Baković (Reference Baković2007) is non-gratuitous feeding, in which the structural description of one process is obscured by a second process that is fed by the first. For example, in Classical Arabic a vowel is epenthesised before an initial consonant cluster (rule (14a)).Footnote ¹³ This then feeds glottal stop epenthesis in (14b), as initial vowels must be preceded by a glottal stop in Classical Arabic.

1. (14)

   

This interaction can be considered opaque because both the triggering environment for vowel epenthesis and its output are altered by the application of glottal stop epenthesis – that is, the resulting word-initial #VCC sequence is not word-initial in the output.

The combined map is 3-ISL. This can be shown fairly easily, as the crucial input–output correspondences are defined in the same word-initial environment, as summarised in Table VI.

Table VI

Abbreviated input/output table for non-gratuitous feeding in Classical Arabic.

When the suffix is /⋊/, an input /V/ is output as [ɁV]. For the same suffix /⋊/, an input /C/ is instead output as λ. This is to withhold a word-initial /C/, as it may be the first member of a word-initial CC sequence, and thus subject to vowel epenthesis. The application of vowel epenthesis is then defined for inputs when the 2-suffix is /⋊C/. If a /V/ follows (row (c)), then vowel epenthesis does not apply, and [CV] is output. If a /C/ follows (row (d)), then both vowel epenthesis and glottal epenthesis apply, and so [ɁVCC] is output. Contrasting derivations for /CVC/ → [CVC] (when neither process is triggered) and /CCVC/ → [ɁVCCVC] (when both processes are triggered, corresponding to (12)) are shown in (15). As illustrated in (15), the interaction between these two processes is 3-ISL, as it can be captured with a scanning window of size 3.

1. (15)

   

3.5 Fed counterfeeding in Tundra Nenets

Kavitskaya & Staroverov (Reference Kavitskaya and Staroverov2010) describe another type of opacity, fed counterfeeding. (16a) gives an example from Tundra Nenets, with the debuccalisation and vowel-deletion rules shown in (16b).

1. (16)

   

In a mapping like (16a.i), we observe counterfeeding: if vowel deletion applied first then debuccalisation would also apply to derive *[taɁ]. But (16a.ii), which in a rule-based analysis proceeds as /t^jimjʌs/ ↦ t^jimjʌɁ ↦ [t^jimjɁ], instead demonstrates feeding. Thus the same two rules can exhibit both feeding and counterfeeding, depending on the input form.

Using the alphabet {ʌ, Ɂ, T, C, V} (where T = {t, d, s, n, ŋ}, C is any consonant aside from /Ɂ/ and those in T, and V is any vowel except /ʌ/), we can show that this combined fed counterfeeding map is 3-ISL. Since /ʌ/-deletion doesn't have a left context, the output of /ʌ/ is λ, no matter what 2-suffix precedes it. This is indicated in rows (a–e) of Table VII, where X denotes any segment.Footnote ¹⁴

Table VII

Abbreviated input/output table for fed counterfeeding in Tundra Nenets.

The situation is similar when the input is T. As the debuccalisation rule has no left context, whenever a T is input it must be withheld until it can be determined whether it is word-final (rows (f–j)). Again, the output of T when the 2-suffix ends in T (row (j)) is T, representing the return of the T in the suffix, which is now known not to be word-final. This is also why the output is T in row (e): the additional input of /ʌ/ verifies that the suffix T is not word-final, and therefore should be output unchanged. Note this is the key to the fed counterfeeding interaction originally shown in (16a.i), where an input /s/ preceding a deleted /ʌ/ escapes debuccalisation.

When an input /Ɂ/ follows a 2-suffix that ends in /ʌ/ (row (k)), the output is also λ, because if (and only if) it is word-final, this will also trigger deletion of /ʌ/. In contrast, if the input following a 2-suffix that ends in /ʌ/ is /C/ or /V/, then the output returns the withheld [ʌ], which we now know will not be deleted (rows (l, m)).

Since these are both word-final processes, the crucial rows of the input/output table (n–w) are those for which the input is /⋉/. When /⋉/ follows the 2-suffix /ʌT/ (row (n)), the context for both deletion and debuccalisation has been found, so the output is [Ɂ⋉]. Debuccalisation also applies when any of the 2-suffixes /CT, VT, TT, ɁT/ (rows (o–r)) are followed by /⋉/. Deletion alone applies when /⋉/ follows the 2-suffix /ʌɁ/ (row (s)). When any 2-suffix that ends in /ʌ/ is followed by /⋉/, the /ʌ/ is deleted, as shown in rows (t–w). (17) illustrates this interaction with example derivations.

1. (17)

   

3.6 Discussion

This concludes our analysis of four distinct types of opaque phonological maps, all of which have been shown to be ISL functions for some value of k. Similar analyses of the other three cases in this typology are presented in Appendix B. Together, these analyses show that a seemingly diverse set of interactions can be given a unified computational analysis based on the common property of ISL. This does not, however, amount to a claim that opacity itself is ISL. Long-distance processes, which are not ISL, can also be involved in opaque interactions. Nonetheless, it is still a non-trivial result that every example in this typology of opaque maps is ISL.

While the object of each analysis presented above was the extension of the opaque interaction as a whole, each case can be (and has been) thought of as an interaction between two individual processes. This raises two important questions. First, given two ISL maps with possibly different k-values, what will the k-value of the map that describes their interaction be? The second question is closely related: is the class of ISL functions closed under composition – that is, is the composition (see note 7) of any two ISL functions guaranteed to also be ISL? We address these two questions in turn.

Table VIII reviews the results of this section and Appendix B, presenting the k-values for each opaque map discussed, along with the k-values for the individual processes of each interaction.Footnote ¹⁵ For ISL maps corresponding to single phonological rules, determining the k-value is straightforward: k is the length of the longest string in the structural description of the process. The longest k-value for one of the interactions, listed in the rightmost column, is 5, for Turkish, whereas the others are either 2 or 3. Note that there is no clear correlation between the size of the k-values for the basic processes and the k-value of the resulting interaction. For example, both epenthesis and assimilation in Lithuanian (§3.2) are 2-ISL, as is their interaction. In contrast, epenthesis in Turkish is 3-ISL and deletion is 4-ISL, whereas their interaction is 5-ISL. Thus the composition of two ISL processes is not simply the larger of their respective k-values, nor their sum. Predicting the k-value of the composition of two ISL processes appears to be a more subtle matter, involving how the output of the second process depends on the output of the first.

Table VIII

The k-values for the ISL maps analysed in §3 and in Appendix B.

Nonetheless, in all of the cases analysed here, there exists some k for which the map that combines the two ISL processes is k-ISL. This is not, however, true generally, as the ISL functions as defined in Chandlee (Reference Chandlee2014) are not closed under composition. A proof of this fact can be found in Appendix B. Thus the interaction of two ISL processes is not itself guaranteed to be ISL. However, subsets of the ISL class may be closed under composition. Chandlee & Lindell (Reference Chandlee, Lindell and Heinzto appear) study ISL maps from a logical perspective, and identify a subclass which excludes the counterexample given in Appendix B, but includes all of the opaque interactions studied in this paper.

In sum, the preceding sections demonstrated that many cases of opacity are ISL for some k, as summarised in Table VIII. In this subsection, we have addressed two important theoretical questions about ISL and map interaction: (i) can we predict the k-value of the interaction of two ISL processes?, and (ii) is the class of ISL functions closed under composition? The answer to both of these questions is currently ‘no’, but ongoing research aims to identify the conditions under which interactions preserve the ISL property.

4.1 Points of comparison

We consider the following points of comparison: typological predictions, learnability, generation and recognition. Typological predictions refer to a theory's predictions as to the kinds of maps that should and should not occur. Learnability refers to the results that have been obtained with respect to how the kinds of grammars the theories posit can be learned. Generation refers to whether algorithms exist which reliably compute a surface form from a given underlying form using the grammar. Recognition refers to the converse of the generation process: given a surface form and grammar, is there a procedure that can recover the possible underlying forms?

All four points of comparison are important. Typologically, it is preferable for theories to neither overgenerate nor undergenerate, though we acknowledge there is room for debate on the nature of this over- and undergeneration. For instance, it can be difficult to decide between two theories that overgenerate in different ways. However, computational complexity is a clear measure for overgeneration. We thus adopt the principle that theories which overgenerate simple patterns (computationally speaking) are to be preferred to theories which overgenerate complex patterns. This gives us a strong starting point from which to further restrict the theory, based on substantive constraints such as phonetic naturalness.

In addition, as human children somehow acquire their native language's phonology, a theory of phonology should provide some guarantee that the grammars it predicts to exist can be learned by provably correct learning algorithms. There are different ways to characterise what it means ‘to learn’ (Kearns & Vazirani Reference Kearns and Vazirani1994, Jain et al. Reference Jain, Osherson, Royer and Sharma1999, de la Higuera Reference Higuera2010), and different types of learning problems in phonology can be identified. None of the results mentioned in this paper are complete solutions to the problem of phonological acquisition. Nonetheless, it ought not be controversial that algorithms which are well understood analytically and computationally efficient provide important landmarks in understanding how a child could generalise from linguistic stimuli. Indeed, theoretical learnability results have played an important role in the literature (Tesar & Smolensky Reference Tesar and Smolensky1996, Reference Tesar and Smolensky1998; see also Heinz & Riggle Reference Heinz, Riggle, van Oostendorp, Ewen, Hume and Rice2011 for a review of the relationship between learnability and phonology).

Finally, it is desirable for there to exist specific algorithms that solve the generation and recognition problems. Generation allows us to reliably compute predictions within a language. Without a generation algorithm, we cannot make reliable predictions about the output form of a given input form. And recognition is a form of parsing, allowing us to reliably interpret surface forms in terms of their potential underlying structure. While recognition may not receive as much attention as generation, recognition algorithms may play a role in some learning problems.

In the remainder of this section, we compare the ISL function theory with rule-based theories like SPE and with OT. We first compare the theories with respect to the generation and recognition problems (§4.2). Then we consider the learnability criterion (§4.3). Finally, we address typology (§4.4). Our conclusion is that, despite some known deficiencies, the ISL theory of phonology compares well, and has sufficient merit to be worthy of further study.

4.2 Generation and recognition

The fact that ISL functions can be characterised by FSTs is significant. The generation and recognition problems are solved for FSTs. Algorithms like the ones mentioned in §2.4 guarantee that the correct output is generated from a given input. Likewise, it is well-known that FSTs can be inverted to do recognition (Beesley & Karttunen Reference Beesley and Karttunen2003). In other words, if the solution to the generation problem is in terms of FSTs, then one automatically obtains a solution to the recognition problem.

Rule-based grammars also have solutions to the recognition and generation problems. This is because they can be faithfully compiled into FSTs, provided it is clear whether they apply simultaneously, left to right, right to left and/or optionally (Johnson Reference Johnson1972, Kaplan & Kay Reference Kaplan and Kay1994). The fact that all maps for phonology can be expressed as a list of ordered SPE-style rewrite rules is strong evidence for the claim that phonological maps are regular (i.e. describable with a FST). (See Karttunen Reference Karttunen and Goldsmith1993 and Heinz Reference Heinz2011a, Reference Heinzb for additional discussion on this point.)

In OT, there are solutions to the generation and recognitions problems under certain assumptions. Frank & Satta (Reference Frank and Satta1998) show that OT grammars can be faithfully compiled into FSTs provided the three conditions in (18) hold. (See Frank & Satta Reference Frank and Satta1998, Karttunen Reference Karttunen, Karttunen and Oflazer1998, Gerdemann & van Noord Reference Gerdemann, van Noord, Eisner, Karttunen and Thériault2000, Jäger Reference Jäger, Kaufmann and Stiebels2002, Riggle Reference Riggle2004 and Gerdemann & Hulden Reference Gerdemann and Hulden2012 for more details.)

1. (18)

   

However, many theoretical phonologists do not accept these assumptions. Correspondence theory is the most widely adopted theory of Gen, but it is not known whether such a Gen defines a regular relation. Also, not all constraints widely used in the literature can be described with FSTs, such as the constraints of the Align family (Eisner Reference Eisner1997). Finally, while some theoretical phonologists have argued for assumption (18c) (e.g. McCarthy Reference McCarthy2003), most do not adopt it. Consequently, OT theories of phonology which fail to adopt these three assumptions lack a comprehensive solution to the generation problem.

There are some other approaches to generation and recognition in OT. For instance, Riggle's (Reference Riggle2004) solution does not require bounding the number of violations constraints assign ((18c)), but it does depend on (18a) and (b). His solution is guaranteed to be correct, provided the map that the OT grammar describes is in fact a regular relation (but not all of them are; one example is discussed below). Another solution is found in Albro (Reference Albro2005), which provides a comprehensive OT analysis of the phonology of Malagasy; it assumes Gen is represented by a mildly context-sensitive grammar.

The above discussion indicates that solutions to the generation and recognition problem under typical assumptions in OT, even if currently absent, may be forthcoming. Nonetheless, their absence contrasts with existing algorithms that reliably solve the generation and recognition problems for SPE and the ISL function theories.

4.3 Learnability

With respect to learnability, there are algorithms which provably learn any ISL function from finitely many examples of (input, output) pairs (Chandlee et al. Reference Chandlee, Eyraud and Heinz2014, Jardine et al. Reference Jardine, Chandlee, Eyraud, Heinz, Clark, Kanazawa and Yoshinaka2014). These algorithms are provably efficient in the size of the input to the learner. Additionally, it is the case that the amount of data required to learn the pattern exactly is polynomial in the size of the target grammar. In fact, Chandlee et al.’s results are quadratic, and Jardine et al.’s linear.

With respect to rule-based grammars, there are some results, but they are not as strong. In each case, the input data is assumed to be (input, output) pairs. Johnson (Reference Johnson1984) shows how to generate all rules consistent with the input data, and Oncina et al. (Reference Oncina, García and Vidal1993) prove that the Onward Subsequential Transducer Inference Algorithm (OSTIA) can learn total subsequential functions in time cubic in the size of the input data. Since many segmental phonological maps appear to be subsequential (Chandlee et al. Reference Chandlee, Athanasopoulou and Heinz2012, Chandlee & Heinz Reference Chandlee and Heinz2012, Gainor et al. Reference Gainor, Lai and Heinz2012, Heinz & Lai Reference Heinz, Lai, Kornai and Kuhlmann2013, Jardine Reference Jardine2016), and since Kaplan & Kay (Reference Kaplan and Kay1994) show how to convert a FST into a rule, this suggests a method for learning rules. However, Gildea & Jurafsky (Reference Gildea and Jurafsky1996) have argued that OSTIA, while well understood analytically, needs more phonology-specific information to be successful on corpus data.

There are numerous results for both the core OT theory and its variants. Many of these results are impressive and analytical. The first is Recursive Constraint Demotion, introduced by Tesar & Smolensky (Reference Tesar and Smolensky1998), which was shown to provably learn OT grammars with a polynomial mistake bound. It has subsequently been shown that established machine-learning techniques can be applied to Harmonic Grammar (Pater Reference Pater2008, Bane et al. Reference Bane, Riggle and Sonderegger2010, Potts et al. Reference Potts, Pater, Jesney, Bhatt and Becker2010), and also to categorical OT (Magri Reference Magri2013). Finally, Tesar (Reference Tesar2014) proves that, under certain conditions, an OT-based learner can learn both a grammar and underlying forms for a map, given that the map is output-driven.

However, to our knowledge there are no analytical results for optimisation-based learners that can learn an entire class of grammars that includes the diversity of opaque maps that we have discussed here. In the absence of analytical results, there are interesting modelling studies which bear on this question. For example, Jarosz (Reference Jarosz, Ólafur Hansson, Farris-Trimble, McMullin and Pulleyblank2016) provides results from simulations demonstrating an algorithm that can successfully learn Harmonic Serialism grammars capable of describing some opaque maps. Also, Nazarov & Pater (Reference Nazarov and Pater2017) provide simulations from a learner capable of learning some opaque maps represented in Stratal Maximum Entropy Grammar. While results based on specific models tested with specific input may in the future lead to more general results, they are at present less conclusive than results based on proven theorems.

4.4 Typology

In this section, we compare the ISL approach to phonological maps with OT and SPE in terms of its generative power (i.e. does it over- or undergenerate the observed typology?). As noted in §2.5, in this paper we focus on generation with respect to computational properties, putting aside any treatment of the important questions of phonetic naturalness, such as the idea that phonological grammars are organised around natural classes and not individual speech sounds. For instance, in the same way that SPE-style rules and OT constraints can be required to refer to natural classes, this could also be required for ISL functions, which would be a further restriction.

Earlier we explained that many phonological maps, including opaque ones, are ISL for some k. However, as Chandlee (Reference Chandlee2014), Chandlee, Eyraud & Heinz (Reference Chandlee, Eyraud, Heinz, Kuhlmann, Kanazawa and Kobele2015) and Chandlee & Heinz (Reference Chandlee and Heinz2018) explain, neither progressive and regressive iterative spreading nor unbounded consonant and vowel harmony are ISL. Consequently, this theory undergenerates.

This undergeneration problem requires adjusting the theory. However, as noted by Chandlee & Heinz (Reference Chandlee and Heinz2018), the change is not expected to be significant. Chandlee, Eyraud & Heinz (Reference Chandlee, Jardine and Heinz2015) show that iterative spreading can be described with a comparable class of functions called Output Strictly Local functions, which differ from ISL in that the output is determined based on a bounded window of the previous output rather than the input.

For long-distance phenomena, an approach is readily available which builds on previous work on phonotactics and the Subregular Hierarchy, a hierarchy of formal languages that are all properly contained by (i.e. are less complex than) the regular languages (Rogers & Pullum Reference Rogers and Pullum2011, Rogers et al. Reference Rogers, Heinz, Fero, Hurst, Lambert, Wibel, Morrill and Nederhof2013). Heinz (Reference Heinz2010) argues that long-distance phonotactic constraints can be characterised by Strictly Piecewise (SP) languages. Another, related, view holds that long-distance phonotactics can be characterised as Tier-based Strictly Local (TSL) languages (Heinz et al. Reference Heinz, Rawal and Tanner2011, McMullin Reference McMullin2016). In the same way that the ISL functions are based on the notion of locality that defines the SL languages, there are likely to be functional counterparts to the SP and TSL classes. These classes are expected to characterise long-distance maps, though the precise nature of these functions is an area of current research. Taken together, this means that the current theory can be modified as follows to address the undergeneration problem: phonological grammars are not just ISL functions, but rather some combination of ISL, OSL, SP and TSL functions. What these functions have in common is they are all subregular.

As for overgeneration, one of the ways in which grammars can overgenerate is to permit maps like majority rules (MR) vowel harmony and sour grapes (SG) vowel harmony (Baković Reference Baković2000, Finley Reference Finley2008, Heinz & Lai Reference Heinz, Lai, Kornai and Kuhlmann2013).Footnote ¹⁷ ISL maps do not overgenerate in this way. This is because (i) every ISL function by definition is also both a regular relation and a subsequential function, and (ii) it has been proven that MR maps are not regular relations and SG maps are not subsequential (Heinz & Lai Reference Heinz, Lai, Kornai and Kuhlmann2013).

Turning to the typological predictions of rule-based grammars, it is generally understood that ordered rules do not undergenerate. They also can describe opaque maps, despite some criticisms (e.g. Baković Reference Baković2007, Reference Baković, Goldsmith, Riggle and Yu2011). With respect to overgeneration, the SG pattern is regular, and therefore describable with an ordered list of rules according to Kaplan & Kay's analysis. On the other hand, rule-based grammars cannot generate non-regular maps like MR.

Turning to optimisation-based theories, it is well-known that classic OT cannot generate many opaque maps (Idsardi Reference Idsardi1998, Reference Idsardi2000, McCarthy Reference McCarthy2007, Buccola Reference Buccola, Morrill and Nederhof2013) – as discussed by Baković (Reference Baković2007), OT analyses of non-gratuitous feeding and cross-derivational feeding are possible and straightforward. In response, many adjustments to classic OT have been proposed, including constraint conjunction (Smolensky Reference Smolensky, Smolensky and Legendre2006), sympathy theory (McCarthy Reference McCarthy1999), turbidity theory (Goldrick Reference Goldrick2000), output-to-output correspondence (Benua Reference Benua1997), stratal OT (Kiparsky Reference Kiparsky1998, Reference Kiparsky2000, Bermúdez-Otero Reference Bermúdez-Otero, Hannahs and Bosch2018), candidate chains (McCarthy Reference McCarthy2007), Harmonic Serialism (McCarthy Reference McCarthy2000), targeted constraints (Wilson Reference Wilson2000), contrast preservation (Łubowicz Reference Łubowicz2003), comparative markedness (McCarthy Reference McCarthy2003) and serial markedness reduction (Jarosz Reference Jarosz, Kingston, Moore-Cantwell, Pater and Staubs2014). See McCarthy (Reference McCarthy2007) for a review, meta-analysis and more references to these proposals.

These approaches all invoke different representational schemes, constraint types and/or architectural changes to classic OT. In comparison, no special modifications are needed to establish the ISL nature of the opaque maps we have studied in this paper. Furthermore, the typological and learnability ramifications of these changes to classic OT are not yet well understood in many cases, though they are the subject of current research (e.g. Nazarov & Pater Reference Nazarov and Pater2017). For instance, it is not obvious whether the results of Recursive Constraint Demotion carry over from classic OT to Stratal OT.

It is also the case that classic OT overgenerates. This is not controversial. It has been shown that non-regular maps are obtainable via the interaction of very simple constraints (Frank & Satta Reference Frank and Satta1998, Riggle Reference Riggle2004, Gerdemann & Hulden Reference Gerdemann and Hulden2012, Heinz & Lai Reference Heinz, Lai, Kornai and Kuhlmann2013). MR vowel harmony is one example (Baković Reference Baković2000, Finley Reference Finley2008). Hansson (Reference Hansson2007) and McMullin & Hansson (Reference McMullin and Ólafur Hansson2015) draw similar conclusions with respect to Agreement by Correspondence. Gerdemann & Hulden's (Reference Gerdemann and Hulden2012) example is given in (19).

1. (19)

   

Under this ranking, an input string a ⁿb ^m maps to a ⁿ if m<n, but to b ^m if n<m. No FST can compute this function (i.e. it is non-regular).

Maps like MR and the one above make computations based on global access to information in the string. In this respect, optimisation misses an important generalisation. When computing the output of phonological maps, the necessary information is contained within substructures of bounded size, which, as this paper shows, are often present in the input representation. This is neither expected nor predicted under global optimisation. On the other hand, it is one of the defining characteristics of ISL functions.

To summarise, both rule-based and optimisation-based grammars overgenerate in a way that ISL maps do not. Additionally, optimisation-based grammars and ISL maps undergenerate when compared to rule-based grammars, but in different ways. ISL maps cannot account for iteration and long-distance phenomena. Optimisation-based grammars struggle with opaque maps, as witnessed by the past two decades of research in this area. We believe that the prospects for extending subregular functions to include long-distance phenomena are bright, and this line of research ought to be pursued.

Figure 4 summarises the typological results. A successful theory of phonology ought to include patterns like Bedouin raising,Footnote ¹⁸ Bedouin opacity and consonant harmony, while excluding sour grapes harmony and majority rules harmony. While no such theory exists to our knowledge, we hope to have convinced readers that extending ISL maps in the ways mentioned above is a route worthy of further research.

Figure 4

Alignment of typological predictions of rule-based theories, classic OT and subregular theory (BO = Bedouin opacity, R = Bedouin raising, CH = consonant harmony, SG = sour grapes harmony, MR = majority rules harmony).

4.5 Summary of theory comparison

A theory of phonology which characterises UR–SR maps as ISL functions provides theoretically strong results for learnability, recognition and generation. With respect to typology, certain types of overgeneration are avoided, such as MR and SG harmony. On the other hand, the theory cannot generate long-distance maps, though it could be modified to include them by generalising additional subregular language classes to functions. Rule-based theories, on the other hand, do not undergenerate at all. They do overgenerate SG harmony, but not MR harmony, as the former, but not the latter, is regular. While some learnability results exist, they were not thoroughly pursued, in part due to the advent of constraint-based theories. Lastly, due to their known correspondence with FSTs, rule-based grammars can also be successfully used for both generation and recognition.

Optimisation-based theories have theoretical results for generation and recognition under certain assumptions, even if they are not widely adopted in practice. There are also learnability results for a variety of optimisation frameworks. With respect to typology, we find both overgeneration and undergeneration. It is interesting to observe that the signature of a successful OT analysis involves complex phenomena being understood as the interaction of simple constraints. But the overgeneration problem is precisely this: complex but strange phenomena emerging from the interaction of simple constraints. One approach is to put the burden of explanation on Con: the right set of constraints will generate the attested patterns, but not ones like MR or SG. This is a reasonable approach, but it misses the forest for the trees. Under this approach, the choice of Con blunts the power of optimisation, to avoid generating non-regular maps. There is an important typological generalisation – that phonological maps are regular – whose explanation is obtusely stated on this line of thinking.