4.1 Equations in the linear system

We first convert the weighting conditions into linear inequalities. For each winner–loser pair, we want an inequality that guarantees that the winner has greater harmony than the loser, as in (3). Weighting conditions like those in (6) are useful for getting a handle on the problem analytically. For the tableau depicted on the left in (10), the weighting condition is (11a), and for the tableau on the right in (10), the weighting condition is (11b).

1. (11)

   

For the numerical optimisations to follow, we make extensive use of the following notation.

1. (12)

   

The w _i variables are the weights assigned by the weighting function W to these constraints. Inequality (12a) expresses the requirement that the Winner₁ output is favoured by the weighting over the Loser₁ output, and (12b) expresses the requirement that the Winner₂ output is favoured by the weighting over the Loser₂ output. These inequalities are the HG equivalents of OT's Elementary Ranking Conditions (Prince Reference Prince2002). They can be directly calculated from a winner–loser pair by subtracting the loser's score on each constraint from that of the winner.

Given a tableau set (T, C), we translate each winner–loser pair in each tableau in T into an inequality statement like the above. A weighting answers the learning problem in (8) for (T, C) if and only if it satisfies all of these inequality statements simultaneously.

4.2 The objective function

All and only the vectors 〈w ₁, w ₂〉 satisfying the inequalities in (12) are solutions to the learning problem (8) for (10). The vectors 〈1, 2〉 and 〈2, 3〉 suffice, as do an infinite number of others.

The structure of linear programming problems gives us an analytically useful way of selecting from the infinitude of possible solutions to a problem like this. The crucial notion is that of an objective function. Throughout this paper, we work with very simple objective functions: just those that seek to minimise the sum of all the weights. Thus, for the two-constraint tableau set (10), the objective function is (13).

1. (13)

   

More generally, if there are n constraints, we seek to minimise the sum of all the weights w _i for 1⩽i⩽n, subject to the full set of inequalities for the system.

However, we have now run into a problem: our optimisation problem is undefined (Chvátal Reference Chvátal1983: 43). The vector 〈1, 2〉 is not a minimal feasible solution, and neither are 〈1, 1.5〉, 〈1, 1.1〉, 〈1, 1.0001〉, etc. Each is better than the previous one according to (13); there is no minimal solution. Thus we can never satisfy (13); whatever solution we find can always be improved upon. The problem can be traced to our use of strict inequalities. In stating the problem this way, we are effectively stating a problem of the form ‘find the smallest x such that x>0’, which is also ill-defined.

It won't do to simply change ‘>’ to ‘≥’, because that would insist only that the winner be at least as good as the losers, whereas our version of HG demands that the winner be strictly better. Thus, to address this problem, we solve for a special constant a. It can be arbitrarily small, as long as it is above 0. It allows us to have regular inequalities without compromising our goal of having the winner win (not tie). This is equivalent to adding the amount a to the weighted sum of the loser's constraint violations. The value of a defines a margin of separation: the smallest harmony difference between an optimum and its nearest competitor. (Such margins of separation are important for the Perceptron convergence proof; see Boersma & Pater Reference Boersma and Pater2008 for an application to HG.)

Our use of the margin of separation a renders certain systems infeasible that would otherwise be feasible. These are the systems in which a winner can at best tie its losing competitors. We want these systems to be infeasible, because we want the winners to be strictly better. But one might wonder whether certain choices of a could rule out systems that we want to judge feasible. For instance, what happens if a is set to be very large? Could this incorrectly rule out a feasible analysis?

The answer is no. We assume that there is no maximal weighting for any constraint, and none of our systems contain the conditions that would impose such a ceiling for particular cases. Thus, assume that the chosen constant is a, and assume also that there is a weighting W for which one of the inequality statements sums to a constant d that is smaller than a. Then we simply find a linear rescaling of W that respects our choice of a rather than d. This rescaling could result in infeasibility only if there were a maximal value for some weight. But we assume that there are no such maxima.

4.3 Blocking zero weights

The next question we address is whether to allow 0 weights. A weighting of 0 is equivalent to cancelling out violation marks. To prevent such cancellation, we can impose additional conditions, over and above those given to us directly by the weighting conditions: for each constraint C _i, we can add the inequality w _i≥b, for some positive constant b. Once again, because we impose no maxima, excluding this subregion does not yield spurious verdicts of infeasibility.

It is worth exploring briefly what happens if we remove the extra non-0 restrictions (if we set the minimal weight b to 0). In such systems, some constraint violations can be cancelled out when weighted, via multiplication by 0. This cancellation occurs when a given constraint is inactive for the data in question, i.e. when it is not required in order to achieve the intended result. For example, our current model returns 〈1, 1, 1〉 as a feasible solution for the small system in (14) (assuming that we set the margin of separation a to 1 and the minimal weight b to 1).

1. (14)

   

In this solution, C ₁ and C ₃gang up on C ₂: with this weighting, neither suffices by itself to beat the loser, but their combined weighted scores achieve the result. However, if we do not ensure that all weights are at least b, then the minimal solutions for these data are 〈1, 0, 0〉 and 〈0, 0, 1〉, with either of C ₁ or C ₃ decisive and the other two constraints inactive. As in this example, imposing a greater than 0 minimum on weights tends to result in solutions that make use of gang effects, while choosing a 0 minimum tends to find solutions that make use of a smaller number of constraints. Exploring the differences between these solutions (as is possible in OT-Help) may help an analyst better understand the nature of the constraint interactions in a system.

4.4 The final form of the system

The linear system derived from (10) using the above procedure is given in Fig. 1, along with a geometric representation. To provide a concrete solution and a visualisation, we've set the margin of separation a to 1 and the minimal weight b to 1.Footnote ⁴ The optimal weighting here is w ₁=1 and w ₂=2. The current version of OT-Help accepts OTSoft files as input, converts them into tableau sets, translates them using the above procedure and then solves them with the simplex algorithm, the oldest and perhaps most widely deployed linear programming algorithm (Dantzig Reference Dantzig1982, Chvátal Reference Chvátal1983, Bazaraa et al. Reference Bazaraa, Jarvis and Sherali2005).

Figure 1

Translation and graph of (10), with the feasible region shaded.

4.5 Further remarks on the translation

Before putting these technical concepts to work solving linguistic problems, we would like to pause briefly to use graphical depictions like the one in Fig. 1 to clarify and further explore some of the decisions we made in translating from tableau sets to linear systems. Because each linguistic constraint corresponds to a dimension, we are limited to two-constraint systems when visualising, but the technique can nonetheless be illuminating.

4.5.1 Infeasibility detection

The graphical perspective immediately makes it clear why some linguistic systems are predicted to be impossible: they have empty feasible regions. Our simple NoCoda/Max example from §2 provides a good case study. Our goal there was to show that HG, like OT, predicts that it is impossible for a single language to allow a /ban/ to surface faithfully as [ban], but for it to penalise just one of the codas in /bantan/, thereby allowing something like [ba.tan] to surface. Here is a tableau set seeking to specify such a language.

1. (15)

   

In Fig. 2, we have transformed this tableau set into a linear system and plotted it. The arrows indicate which region the two main inequalities pick out. There is no area common to both of them, which is just to say that the feasible region is empty.

Figure 2

The linear view of tableau set (15). The intersection of all the areas picked out by the inequalities is empty, which is just to say that no grammar picks out the set of specified winners.

4.5.2 Margins of separation

We asserted in §4.2 that the precise value of a does not matter for addressing the fundamental learning problem (8). Figure 3 helps bring out why this is so. This figure differs minimally from the one in Fig. 1, in that the value of a here is 3 rather than 1. This narrows the bottom of the feasible region, and, in turn, changes the minimal solution, from 〈1, 2〉 to 〈2¼, 5¼〉, but the important structure of the system is unchanged.

Figure 3

The system in Fig. 1, but with the value of a set to 3, rather than 1. The feasible region has narrowed at the bottom, and the solution is different, but the basic structure remains the same.

One's choice of the margin of separation a can have consequences for how the solution generalises to unseen data, that is, to tableaux that are not included in the learning data. Suppose, for example, that we evaluate the candidates in the following new tableau, using the weights found with each of the two values of a above.

1. (16)

   

With a=3, the optimal weighting vector is 〈2¼, 5¼〉, which favours Output_3a. With a=1, the optimal weighting vector is 〈1, 2〉, which favours Output_3b.

4.5.3 Stopping short of optimization

In discussing the objective function (§4.2), we emphasised finding minimal solutions. While knowing which is the minimal solution can be illuminating, it goes beyond the learning question (8), which simply asks whether there is a feasible solution at all. Our approach can be simplified slightly to address a version of this more basic question, with a resulting gain in efficiency. To see this, we need to say a bit more about how the simplex algorithm works.Footnote ⁵

The simplex algorithm begins by setting all the weights to 0 and then pivoting around the edge of the feasible region until it hits the optimal solution according to the objective function. Figure 4 illustrates for one of the basic two-variable systems discussed by Cormen et al. (Reference Cormen, Leiserson, Rivest and Stein2001: 773). The arrows show one direction that the simplex might take; which direction it travels depends on low-level implementation decisions.

Figure 4

The simplex algorithm begins at the all-0s solution (the origin), and then pivots around the edge of the feasible region until it finds the vector that does best by the objective function.

For this problem, the all-0s solution is inside the feasible region, so it provides a starting point. However, for all the systems arrived at via the conversion method of §4, setting all the weights to 0 results in an infeasible solution. For this reason, our solver always goes through two phases. In phase one, it constructs from the initial system an auxiliary system for which the all-0s solution is feasible and uses this system to move into the feasible region of the initial problem (ending phase one). In Fig. 1, this auxiliary program takes us from the origin of the graph to the point 〈1, 2½〉, which is a feasible solution. The phase two optimisation then brings us down to 〈1, 2〉, which minimises the objective function.

The auxiliary program also provides us with a means for detecting infeasibility. One of the central pieces of this auxiliary program is a new artificial variable, w ₀. After we have solved the auxiliary program, we check the value of this variable. If its value is 0, then we can safely remove it and, after a few additional adjustments, we have a feasible solution to the original problem. If its value is not 0, however, then it is crucial to our finding a solution in the first place, thereby indicating that the initial problem has no solutions. This is the source of the verdict of ‘infeasible’ – the linguist's cue that the grammar cannot deliver the desired set of optimal candidates.

Thus the question of whether there is a feasible weighting is answered during phase one of the simplex, with phase two devoted to potential improvements with regard to the objective function. If such improvements are not of interest, then we can stop at the end of phase one.

5.1 Cumulative constraint interaction in Lango

Lango has a ten-vowel system, with five ATR vowels [i e u o ə] and five corresponding RTR vowels [ɪ ∊ ʊ ɔ a]. The following examples of ATR spreading show that it targets RTR vowels in both suffixes (17a–d) and roots (17e–h), in other words, that ATR spreads left-to-right and right-to-left. We have omitted tone from all transcriptions.

1. (17)

   

These examples also show that ATR spreads from high vowel triggers (17b, d–h) as well as from mid vowels (17a, c), and from both front (17e, f) and back vowels (17a–d, g, h). The examples also show that it crosses consonant clusters (17d–g) and singletons (17a–c, h). Finally, they show that it targets high vowels (17e, g), mid vowels (17a, b, f, h) and low vowels (17c, d).

For each of these options for trigger, directionality, intervening consonant and target, there is a preference, which is instantiated in the absence of spreading when that preference is not met. The preferences are listed in (18), along with examples of the failure to spread under dispreferred conditions, as well as references to the minimally different examples in (17) in which ATR spreading does occur in the preferred environment.Footnote ⁷

1. (18)

   

We would like an account of the harmony pattern that encodes each of these preferences with a single constraint. No such account currently exists in either OT or in rule-based approaches, as we discuss in §5.2. We now show that such an account is available under the assumption that constraints are weighted.

We follow Smolensky (Reference Smolensky, Smolensky and Legendre2006) in ascribing the Lango trigger and directionality preferences to constraints on the heads of feature domains, though our implementation differs somewhat in the details. Headed domain structures for ATR are illustrated in (19b) and (19d), in which the ATR feature domain spans both vowels. In (19b) the head is on the rightmost vowel, and in (19d) the head is leftmost. Unlike Smolensky (Reference Smolensky, Smolensky and Legendre2006), we assume that a feature domain is minimally binary – a relation between a head and at least one dependent. In the disharmonic sequences in (19a) and (19c), the ATR feature is linked to a single vowel, and there is no head–dependent relation. The assumption that the ATR vowels in (19a) and (19c) are not domain heads is crucial to our definition of the constraints on triggers below. In these representations, a vowel unspecified for ATR is RTR; the use of underspecification here is purely for convenience.

1. (19)

   

We assume that it is definitional of the head of the domain that it is faithful to its underlying specification: a head of an ATR domain is underlyingly ATR.

For spreading to occur, there must be a constraint that disprefers representations like those in (19a) and (19c) relative to (19b) and (19d) respectively. We adopt a single constraint that penalises both (19a) and (19c): Spread[ATR] (see Wilson Reference Wilson2003, Smolensky Reference Smolensky, Smolensky and Legendre2006, Jurgec Reference Jurgec2009 and McCarthy Reference McCarthy2009 for alternative formulations of a spreading constraint).

1. (20)

   

Since ATR harmony applies between roots and suffixes in Lango, the domain x in (20) must include them and exclude prefixes.

The transformation of an underlying representation like (19a) into a surface representation like (19b) is an instance of R-L spreading, which is dispreferred in Lango. The representation in (19b) violates the constraint in (21).Footnote ⁹

1. (21)

   

For underlying (19a), Head-L and Spread[ATR] conflict: Spread[ATR] prefers spreading, as in (19b), while Head-L prefers the faithful surface representation (19a).

The transformation of an underlying representation like (19c) into a surface representation like (19d) is an instance of spreading from a mid trigger, which is also dispreferred in Lango. This violates the constraint in (22), which also conflicts with Spread[ATR].

1. (22)

   

Similarly, front triggers are preferred by Head[front].

1. (23)

   

As for the constraint preferring spreading across singleton consonants, we follow Archangeli & Pulleyblank (Reference Archangeli and Pulleyblank1994) in invoking a locality constraint.

1. (24)

   

And finally, as the constraint penalising spreading to a non-high target, we follow Archangeli & Pulleyblank (Reference Archangeli and Pulleyblank1994) and Smolensky (Reference Smolensky, Smolensky and Legendre2006) in using a co-occurrence constraint.

1. (25)

   

With this large set of markedness constraints that can conflict with the pro-spreading constraint Spread[ATR], faithfulness constraints are not necessary to characterise the patterns of blocking and spreading we have examined, and so we use only markedness constraints in the analysis we present here. A complete analysis would also include the faithfulness constraints violated by spreading (e.g. Ident[ATR]) and faithfulness constraints that penalise alternative means of satisfying Spread[ATR] (e.g. Max for segment deletion). We exclude these for reasons of space only.

Like Smolensky (Reference Smolensky, Smolensky and Legendre2006), we consider as inputs all bisyllabic sequences containing one ATR and one RTR vowel. The potential trigger ATR vowel is either high front [i], high back [u] or mid [e]. The potential target RTR vowel is either high [ɪ] or mid [∊]. We illustrate the analysis with just this subset of the vowels to make the presentation as clear as possible; some of the exact combinations are not attested in (17) and (18) or in Bavin Woock & Noonan (Reference Bavin Woock and Noonan1979) (e.g. the potential mid trigger is in fact [o] in (17) and (18)). For each ATR/RTR pair, we consider sequences with both orderings of the vowels, and for each of these, we consider inputs with intervening singletons and clusters. For each of these inputs, we consider two candidates: the faithful one, and one in which the input RTR vowel surfaces as ATR. The unfaithful candidates are assumed to have the structure illustrated in (19b, d), where the underlying RTR vowel is parsed as the dependent in the ATR domain.

In Table I, we provide a subset of the inputs, chosen for reasons we discuss below, along with the two candidates. The optimal form is labelled the winner, and the suboptimal candidate is labelled the loser (Prince Reference Prince2002). A ‘W’ in a constraint column indicates that the constraint favours the winner, and an ‘L’ indicates that the constraint favours the loser. All of the constraints assign maximally one violation, so a constraint that favours the winner is violated once by the loser, and a constraint that favours the loser is violated once by the winner. The Spread[ATR] constraint assigns a W when the optimal form has undergone spreading, and an L when the optimal form does not. All of the other constraints assign Ls in some cases of spreading, and Ws in some cases when the candidate with spreading is suboptimal.

Table I

Informative winner-loser pairs for Lango vowel harmony, with constraint weights and margins of separation.

There is no OT ranking of these constraints that will correctly make all of the winners optimal. None of the constraints prefers only winners, and so Recursive Constraint Demotion will immediately stall.

The topmost row shows the weights found by submitting these winner–loser pairs to the implementation of our linear programming-based solver in OT-Help. The rightmost column shows the resulting margin of separation between the optimum and its competitor, i.e. the difference between the harmony scores of the winner and the loser. Since, in this case, the constraints assign a maximum of one violation, the difference between the violation score of a winner and a loser on a given constraint is at most 1. Therefore, the margin of separation is simply the sum of the weights of the constraints that prefer the winner minus the sum of the weights that prefer the loser. The fact that these numbers are always positive shows that winners are correctly optimal under this weighting.Footnote ¹⁰

The first six winner–loser pairs contrast L-R spreading and R-L spreading across an intervening singleton. The first three are input configurations that can yield L-R spreading, since the ATR vowel is on the left. Spreading is always optimal, even with a target mid vowel, which violates ATR[high] when it harmonises. We have left out inputs with potential target high vowels, since with this constraint set, if spreading targets a mid vowel, it is guaranteed to target high vowel in the same context. ATR[high] penalises spreading to mid vowels, and there is no constraint that specifically penalises spreading to high vowels.

The next three inputs (T4–6) are ones that can yield R-L spreading, since the ATR vowel occurs in the second syllable. Spreading in fact occurs with high triggers (T4–5), but not mid ones (T6). To illustrate the case in which spreading fails to occur, we include only an input with a potential high target /ɪ/, since, if a high vowel in a certain environment fails to undergo spreading, a mid vowel is guaranteed to fail as well.

The blocking of spreading in T6 is due to the joint effects of Head[high] and Head-L: the sum of their weights is greater than the weight of Spread[ATR]. An analysis in terms of such a gang effect is necessary because neither Head[high] alone (as in T3) nor Head-L alone (as in T4 and T5) is sufficient to override spreading. This is thus one source of difficulty for an OT analysis with these constraints: if either Head[high] or Head-L were placed above Spread[ATR] to account for T6, the wrong outcome would be produced for one of T3–5.

Inputs T7–9 provide the conditions for L-R spreading across a cluster. Spreading is blocked with a mid trigger (T9), in contrast to L-R spreading across a singleton (T3). Again, we include only the input with the potential high target to illustrate blocking, since spreading to a mid target violates a proper superset of the constraints. Blocking here is due to the combined effects of Head[high] and Local-C, whose summed weights exceed that of Spread[ATR]. That Local-C alone does not override Spread[ATR] is shown in T7–8. Again, since cumulative interaction is needed to get the correct outcome with this constraint set, OT ranking is not sufficiently powerful to deal with this set of winner-loser pairs.

Finally, inputs T10–12 illustrate the least preferred context for spreading: when the ATR vowel is on the right, and a cluster intervenes. Here, and in no other context, spreading is blocked if the trigger is back and the target is mid. This outcome is shown in T11, which can be compared with T2, 5 and 8, in which spreading does occur in other contexts. This is a gang effect between four constraints, Head-L, Local-C, Head[front] and ATR[high], whose summed weight exceeds that of Spread[ATR]. That no set of three of these constraints is sufficiently potent to overcome Spread[ATR] is illustrated by inputs T5, 8, 10 and 12, whose optimal outputs have spreading that violates one of the four possible three-membered sets of these constraints. We do not include potential mid triggers in the set of inputs, since R-L spreading already fails to occur across a singleton (T6), and spreading across a cluster also violates Local-C.

In sum, the cumulative effect of any of the following three sets of constraints overcomes the demands of Spread[ATR].

1. (26)

   

No other set of constraints that does not include all of the members of one of the sets in (26) is sufficiently powerful to override Spread[ATR]: spreading occurs in all other contexts. A correct constraint weighting must simultaneously meet the conditions that the sum of the weights of each of the sets of constraints in (26) exceeds the weight of Spread[ATR], and that the sum of the weights of each of these other sets of constraints is lower than the weight of Spread[ATR]. OT-Help allows such a weighting to be found easily.

5.2 Comparison with alternatives

If the constraints in the previous section were considered either inviolable, as in theories outside of HG and OT, or rankable, as in OT, they would be insufficient for analysis of the Lango paradigm. In this section, we consider extant analyses constructed under each of these assumptions about the activity of constraints. We show that they suffer in terms of both generality and restrictiveness.

In their parametric rule-based analysis, Archangeli & Pulleyblank (Reference Archangeli and Pulleyblank1994) posit five rules of ATR spreading. Each rule specifies directionality and optional trigger, target and locality conditions. These are schematised in Table II. Cells left blank indicate that the rule applies with all triggers, targets or intervening consonants.

Table II

The rules of Archangeli & Pulleyblank (1994), each of which specifies directionality and optional trigger, target and locality conditions. Cells left blank indicate that the rule applies with all triggers, targets or intervening consonants.

The conditions are inviolable constraints on the application of the rules. Because of their inviolability, they must be limited to apply only to particular rules: none of them are true generalisations about ATR spreading in the language as a whole. Even though the directionality, trigger and locality preferences do not state completely true generalisations, they have broad scope in the ATR system of Lango, and must therefore be encoded as constraints on multiple rules. Thus inviolability entails the fragmentation of each generalisation across separate formal statements.

By encoding the conditions as parametric options for rules, Archangeli & Pulleyblank succeed in relating them at some level, but, in the actual statement of the conditions on spreading in Lango, there is a clear loss of generality in comparison with our weighted constraint reanalysis.Footnote ¹¹ We can further note that there exists no proposal for how a learner sets such parameters for spreading rules (see Dresher & Kaye Reference Dresher and Kaye1990 on metrical parameters). Correct weights for our constraints can be found not only with linear programming's simplex algorithm, but also with the Perceptron update rule (Pater Reference Pater2008; see also Boersma & Pater Reference Boersma and Pater2008) and a host of other methods developed for neural modelling and machine learning.

Along with this loss of generality, there is a loss of restrictiveness.Footnote ¹² In Archangeli & Pulleyblank's parametric rule system, any set of rules with any combination of conditions can coexist in a language. Davis (Reference Davis1995) and McCarthy (Reference McCarthy1997) discuss this aspect of the theory with respect to disjoint target conditions on two RTR-spreading rules; here we consider the further possibilities introduced by trigger and locality conditions. One notable aspect of the Lango system is that L-R spreading is ‘stronger’ in all respects: there is no environment in which R-L spreading applies more freely with respect to any of the conditions. This ‘uniform strength’ property is predicted by the HG analysis, but not by the one using parametric rules. As Davis and McCarthy show, the latter theory allows one rule to apply more freely with respect to one condition, and another rule to apply more freely with respect to another condition. For example, with the following parameter settings, L-R spreading targets only high vowels, while R-L spreading has only high vowels as triggers. The set of triggers is unrestricted for L-R spreading, whereas the set of targets is unrestricted for R-L spreading.

Table III

Parameter setting in which L-R spreading targets only high vowels, while R-L spreading has only high vowels as triggers.

To see that this system is impossible in HG, we can consider the required weighting conditions. Along with Head-L, violated by R-L spreading, we include in our constraint set Head-R, which penalises L-R spreading. The weighting conditions are illustrated in Table IV, using the comparative format.

Table IV

Inconsistent weighting conditions for a hypothetical pattern.

L-R spreading is illustrated in the top two rows: ATR can spread from a mid vowel, violating Head[high], but not to a mid vowel, which would violate ATR[high]. R-L spreading, on the other hand, can violate ATR[high], as in the third row, but not Head[high], as in the last one.

Recall that for the winners to be correctly optimal, in each row the sum of the weights of the constraints assigning Ws must be greater than the sum of the weights of the constraints assigning Ls. The resulting inequalities are in fact inconsistent. When this problem is submitted to OT-Help, it returns a verdict of infeasible.

By imposing other combinations of conditions on parameterised rules, there is a range of systems that one can create in which R-L spreading is stronger in one respect, and L-R is stronger in another. None of these can be generated by weightings of our constraints, since they always require inconsistent weighting conditions like those illustrated in Table IV. The general inability of HG to generate a system of this type can be understood as follows.Footnote ¹³ If there is a condition on spreading that applies in one direction but not another, then the sum of the weights of the constraints violated by spreading in the banned direction must be greater than the sum of the weights violated by spreading in the allowed direction (since only the former can exceed the constraint(s) motivating spreading, like our Spread). By assumption, the constraints violated under any target, trigger or locality condition are the same for both directions of spreading. Therefore, this requirement reduces to the statement that the weight of the constraint(s) violated specifically by spreading in the banned direction (e.g. Head-R) must be greater than in the permitted one (e.g. Head-L). From this it should be clear why imposing a second condition on spreading that holds only in the opposite direction would result in inconsistency amongst the weighting conditions.

Smolensky (Reference Smolensky, Smolensky and Legendre2006)'s analysis of Lango in terms of conjoined constraints pursues a similar strategy to that of Archangeli & Pulleyblank (Reference Archangeli and Pulleyblank1994). Since OT does not allow the pattern to be analysed in terms of fully general constraints, Smolensky uses constraint conjunction to formulate complex constraints in terms of more basic formal primitives, much in the same way that Archangeli & Pulleyblank use parameterisation of rules. Again, we find the same basic constraints instantiated multiple times in the analysis, this time across conjoined constraints. To facilitate comparison with our analysis, we show this using the basic constraints from §5.1, rather than Smolensky's own.

To get spreading from high vowel triggers L-R, but not R-L, we conjoin Head[high] and Head-L. For spreading across clusters only from high vowels, we conjoin Head[high] and Local-C. Each of these conjoined constraints is violated when both of the basic constraints are violated. In Table V, we show how the conjoined constraints can resolve two of the sources of inconsistency in the failed OT analysis, using our constraint set from §5.1. In this table, the left-to-right ordering of the constraints provides a correct ranking (the dashed lines separate constraints whose ranking is indeterminate). The first two rows show the conjoined constraint analysis of spreading from mid vowels only L-R, and the second two show the analysis of spreading across clusters from only high vowels.

Table V

The use of local conjunction to resolve inconsistency in the OT analysis of Lango.

Here Head[high] appears in three constraints, much as the high trigger condition is imposed on multiple rules in Table III. Thus the conjoined constraint analysis also succeeds only at the cost of a loss of generality relative to the weighted constraint analysis. And, like the parametric theory, there is no learning algorithm for constraint conjunction (Smolensky Reference Smolensky, Smolensky and Legendre2006: 139).

Furthermore, it shares with the parametric analysis the same loss of restrictiveness identified above. To show this, we provide in Table VI a local conjunction analysis of the hypothetical pattern in which only L-R spreading is triggered by mid vowels (due to conjoined Head[high]&Head-L), and only R-L spreading targets mid vowels (due to conjoined ATR[high]&Head-R).

Table VI

The use of local conjunction to resolve inconsistency in the analysis of a hypothetical language.

For other cases in which local constraint conjunction in OT generates patterns not produced by the unconjoined versions of the basic constraints in HG, see Legendre et al. (Reference Legendre, Sorace, Smolensky, Smolensky and Legendre2006) and Pater (to appear).

The comparison of the typological predictions of the three analyses highlights an important general point about comparisons between theories of constraint interaction, which might be easy to overlook. One might be tempted to favour a less powerful theory of constraint interaction on the grounds that it will offer a more restrictive theory of linguistic typology. However, the predictions of a theory of constraint interaction also depend on the contents of the constraint set. Insofar as a more powerful theory of constraint interaction allows attested patterns to be analysed with a more restricted constraint set, the resulting typological predictions are likely to be in some ways more restrictive. This is just as true of comparisons between HG and OT as it is of comparisons between ranked and inviolable constraints.

We offer the Lango case study as a concrete illustration of this general point. We are not asserting that it is a decisive argument in favour of HG over OT. We offer it instead in the hope that it will inspire further use of HG in linguistic analysis. There are a number of unresolved empirical issues surrounding Lango vowel harmony (see note 5) and the related typology. In recent work, McCarthy (Reference McCarthy2009) surveys the known cases in which bidirectional harmony has stronger restrictions on spreading in one direction than another, and concludes that all are doubtful for one reason or another. McCarthy's critical survey is in fact driven by the inability of his proposed constraint set to produce such patterns when they interact through OT ranking. Further cross-linguistic work driven by the current positive HG results may well yield a different outcome. Not only is further empirical study required to choose between HG and OT, but much further theoretical work is also needed to determine the ways in which HG and OT constraint sets can differ in analyses of existing languages, and the ways in which the resulting theories differ in their predictions. As we show in the following sections, OT-Help is invaluable not only in conducting analyses of individual languages in HG, but also in determining the predictions that constraint sets make in HG and OT.

6.1 Typology calculation

In OT, a language is a set of optimal forms picked by some ranking of the constraints, and the predicted typology is the set of all the sets of optima picked by any ranking of the constraints. OTSoft (Hayes et al. Reference Hayes, Tesar and Zuraw2003) determines the predicted typology by submitting sets of optima to the Recursive Constraint Demotion algorithm (RCDA) (Tesar & Smolensky Reference Tesar and Smolensky1998a), which either finds a ranking or indicates that none exists. OT-Help implements the RCDA as well as our linear programming approach, so we can use it to conduct typological comparisons between the two theories.

OTSoft builds up the typology by using an iterative procedure that adds a single tableau at a time to the RCDA's dataset. When a tableau is added to the dataset, the sets of optima that are sent to the RCDA are created by adding each of the new tableau's candidates to each of the sets of feasible optima that have already been found for any previously analysed tableaux. The RCDA then determines which of these new potential sets of optima are feasible under the constraint set. This procedure iterates until all of the tableaux have been added to the dataset. This is a much more efficient method of finding the feasible combinations of optima than enumerating all of the possible sets of optima and testing them all. OT-Help uses this procedure for both HG and OT.

6.2 The typology of positional restrictions

In the analysis of Lango, we pointed out that one can compare the typological predictions of HG and OT only with respect to the constraint sets that each framework requires to analyse some set of attested phenomena. In that discussion, we compared HG to OT with local constraint conjunction, showing that the less restricted constraint sets permitted by local conjunction yielded less restrictive predictions for typology. Here, we compare HG and OT using non-conjoined constraints, showing again that the greater power of HG can allow for a more restrictive theory. Our example of positional restrictions is drawn from Jesney (to appear), to which the reader is directed for a more detailed discussion; our aim here is only to show how the example illustrates this general point.

Research in OT makes use of two types of constraint to analyse what seems to be a single phenomenon: the restriction of phonological structures to particular prosodic positions. These two types of constraint – positional markedness (e.g. Itô et al. Reference Itô, Mester and Padgett1995, Zoll Reference Zoll1996, Reference Zoll1998, Walker Reference Walker, Féry, Green and van de Vijver2001, Reference Walker2005) and positional faithfulness (e.g. Casali Reference Casali1996, Beckman Reference Beckman1997, Reference Beckman1998, Lombardi Reference Lombardi1999) – capture many of the same phenomena in OT, but neither is sufficiently powerful on its own to account for the full set of attested positional restrictions. In HG, however, positional markedness constraints are able to capture a wider range of patterns, making positional faithfulness unnecessary for these cases.

Positional markedness constraints directly restrict marked structures to the ‘licensing’ position. Given voicing as the marked feature, for example, the constraint in (27a) disprefers any surface instance of [+voice] that appears unassociated with an onset segment, and the constraint in (27b) disprefers any surface instance of [+voice] that appears unassociated with the initial syllable.

1. (27)

   

To illustrate the differences between HG and OT, we consider a language which allows both of the contexts identified in the constraints above – i.e. onsets and word-initial syllables – to license the marked [+voice] feature. In such a language, /badnabad/ would surface as [bad.na.bat], with devoicing only in the coda in a non-initial syllable. Table VII shows how this language can be analysed in HG with our two markedness constraints and a single non-positional faithfulness constraint.

Table VII

A successful HG analysis of a language in which both onsets and word-initial syllables license [+voice].

As in the Lango example, the winner and loser always differ by a maximum of one violation, so we can indicate a preference for each with ‘W’ and ‘L’, instead of indicating the degree of preference numerically. The first row compares the desired optimum to an alternative that devoices all obstruents in non-initial syllables. The loser does better on Voice-σ₁, at the expense of Ident[voice]. The second row compares the winner to a loser that devoices all codas, which improves on VoiceOnset, again at the expense of Ident[voice]. These two comparisons require each of the markedness constraints to have values lower than that of the faithfulness constraint. The last row compares the winner to the fully faithful candidate, which incurs violations of both markedness constraints. This comparison requires the sum of the weights of the markedness constraints to exceed that of the faithfulness constraint. The input /bad.na.bad/ will thus surface as [bad.na.bat], provided that the individual weights of the markedness constraints are insufficient to overcome the weight of Ident[voice], but the summed weights of the markedness constraints together are. Table VII shows a successful HG analysis. In each row, the sum of the weights of the constraints preferring the winner is greater by 1 than the sum of the weights preferring the loser.

There is no OT ranking that will make the winner correctly optimal in Table VII; no constraint assigns only Ws, and so Recursive Constraint Demotion fails. Analysing this type of pattern in OT requires positional faithfulness constraints like those defined in (28).

1. (28)

   

The OT analysis with positional faithfulness constraints is shown in Table VIII. Here, we include general *Voice and Ident[voice] constraints, along with the positional faithfulness constraints defined above. The left-to-right ordering of the constraints is a correct ranking (the relative ordering of the two positional faithfulness constraints is not crucial).

Table VIII

A successful OT analysis using positional faithfulness to license [+voice] in both onsets and word-initial syllables.

While positional faithfulness constraints are required in OT to capture this pattern of licensing in onset and initial syllables, there are other domains where positional faithfulness constraints pose problems. A version of OT with positional faithfulness makes incorrect predictions regarding the realisation of ‘floating features’ and other derived structures, for example, wrongly preferring them to target weak positions (Ito & Mester Reference Ito and Mester2003, Zoll Reference Zoll1998). To see this, we consider an input with a voice feature introduced by a second morpheme (/vce+katnakat/). The desired optimum in this sort of case would realise the feature in a strong position where it is generally licensed – e.g. [gatnakat], with voicing surfacing on the initial onset. This is the outcome predicted by positional markedness, but not by positional faithfulness, as Table IX shows. Positional faithfulness constraints prefer that floating marked features be realised in contexts that are not normally licensers, like the non-initial coda in the loser [kat.na.kad].

Table IX

A situation in which positional markedness constraints are required in OT.

Cases like these, where positional faithfulness and positional markedness each account for a subset of the attested phenomena, have led to a version of OT that includes both types of constraint. A simple continuation of the examples above illustrates the typological consequences. We submitted tableaux for each of the inputs /badnabad/ and /vce+katnakat/ to OT-Help. For HG, we included only the positional markedness constraints, along with *Voice and Ident[voice], while for OT we also included the positional faithfulness constraints. The results are given in Table X. The potentially optimal outputs for /badnabad/ are shown in the first column, and the potentially optimal outputs for /vce+katnakat/ are shown in the top row. Cells are labelled with the name of the theory that makes the row and column outputs jointly optimal.

Table X

Typological predictions for HG with only positional markedness constraints and OT with both positional markedness and positional faithfulness constraints.

The HG results with positional markedness seem to match what is generally found typologically. The full typology may not be found for obstruent voicing, but it is found across the larger set of cases that includes positional restrictions and floating feature behaviour for other structures (see Jesney, to appear for documentation). OT with both positional faithfulness and positional markedness predicts that floating features can dock on any of the four positions defined by the two parameters initial vs. non-initial syllable and onset vs. non-onset. Thus, all of the docking sites for /vce+katnakat/ can be made optimal, indicated in Table X by the label OT in all columns. In addition, there is practically no predicted relation between the positions in which a feature is generally permitted and where floating feature docking will occur. For example, this version of OT can generate a language in which voicing is generally restricted to onsets (/badnabad/, [bat.na.bat]), but in which a floating [+voice] feature docks onto either a final coda (/vce+katnakat/, [kat.na.kad]) or a medial one (/vce+katnakat/, [kad.na.kat]).

Further research is required to determine whether a version of HG without positional faithfulness constraints can indeed deal with the full range of phenomena attributed to these constraints in OT. These initial results suggest that the pursuit of such a theory may yield a resolution to a long-standing problem in OT. Furthermore, since there is not a subset relation in the types of languages generated by the two theories of constraints and constraint interaction illustrated in Table X, this example illustrates the general point that a fleshed-out theory of some set of attested phenomena in HG will likely be in some ways both less restrictive and more restrictive than an OT one.

6.3 Gradient Alignment and Lapse constraints

We now turn to an example concerning the typological spaces determined by two different classes of constraint that have been used for stress typology in OT. McCarthy & Prince (Reference McCarthy and Prince1993) propose an account of stress placement in terms of Alignment constraints, which demand coincidence of edges of prosodic categories. Gradient Alignment constraints are ones whose degree of violation depends on the distance between the category edges: roughly, if x should be at, say, the leftmost edge of a certain domain and it surfaces n segments (syllables) from that edge, then x incurs n violations for the candidate containing it. Kager (Reference Kager2005) proposes an alternative account of stress placement in OT that replaces gradient Alignment constraints with a set of Lapse constraints, which penalise adjacent unstressed syllables in various environments, assigning one mark per violation, as with normal markedness constraints.

To examine the typological predictions of the two accounts, Kager constructed OTSoft files (Hayes et al. Reference Hayes, Tesar and Zuraw2003) with a set of candidate parsings for words from two to nine syllables in length. Separate files contained the appropriate violation marks for each constraint set. For each of these, there were separate files for trochaic (left-headed) feet and for iambic (right-headed) feet (here we discuss only the trochaic results). Using OTSoft, Kager found that the gradient Alignment constraint set generated 35 languages, while the one with Lapse constraints generated 25.

We used OT-Help to replicate Kager's experiment, using both OT and HG. The results for the two constraint sets discussed above, derived from OTSoft files prepared by Kager, are shown in Table XI. We provide the number of languages that each combination of constraints and mode of interaction predicts, out of a total of 685,292,000 possible combinations of optima.

Table XI

Number of predicted languages.

For both constraint sets, HG generates all the languages that OT does. HG also generates a significant number of languages that OT does not.

A primary source of this dramatic increase is the manner in which gradient Alignment constraints assign violation marks. To illustrate, we show four potential parses of a six-syllable word, and the violations they incur on two constraints. Foot edges are indicated by parentheses, and prosodic word edges by square brackets. Align-L(Ft, Wd) demands that the left edge of every foot be aligned with the left edge of the word and is violated by each syllable intervening between these two edges. Parse-σ is violated by every syllable that fails to be parsed into a foot.

1. (29)

   

Align-L(Ft, Wd) and Parse-σ conflict in that every foot added after the leftmost one satisfies Parse-σ at the cost of violating Align-L(Ft, Wd). This cost increases as feet are added: the second foot from the left adds two violations, the third one adds four and so on. This increasing cost interacts with weighting to produce a rich typology. With an appropriate weighting (e.g. a weight of 1 for Align-L(Ft, Wd) and a weight of 2 for Parse-σ), a second foot will be added to avoid violating Parse-σ, but not a third one: (29b) emerges as optimal. This outcome would be impossible in HG, as it is in OT, if each non-leftmost foot added the same number of violations of Align-L(Ft, Wd) (or whatever constraint replaces it).Footnote ¹⁴

The HG typology with Lapse constraints is much closer to that of OT, but it still yields more than a threefold increase in predicted languages. We believe that it would be a mistake to take this sort of result to argue definitively for OT. First, it was arrived at using a constraint set designed for OT. As we have shown in §§5 and 6.2, weighted interaction allows for different constraints than those used in OT, and these possibilities must be further explored to better understand the theory and how it differs from OT. Second, the result also depends on a particular mode of evaluation: here, the entire representation is evaluated once and only once by the entire set of constraints. As Pater (Reference Pater2009b, to appear) shows, changing assumptions about mode of evaluation yields positive results for HG typology, in addition to those that McCarthy (Reference McCarthy, BakoviĆ, Ito and McCarthy2006, Reference McCarthy2007, Reference McCarthy2009) demonstrates for OT (see also Pruitt Reference Pruitt2008 on stress in Serial OT).

6.4 A typological correspondence between OT and HG

The previous simulation highlights the fact that OT and HG can produce quite different typological predictions. However, as we emphasised in the introduction, the two frameworks do not invariably diverge. The present section describes a simulation involving a fairly complex set of constraints for which OT and HG deliver identical typological predictions. The result is especially striking in light of the fact that some of the constraints are gradient Alignment constraints of the sort that produced a large difference in the previous section.

The simulation involves the following set of constraints.

1. (30)

   

The candidate set for the simulation consisted of all logically possible parses of words of two to five syllables in length into left- and right-headed bisyllabic feet, with main stress on either one of the feet in the four- and five-syllable words. The parses are all exhaustive, up to the limits imposed by the binary minimum; there is no more than one unparsed syllable per word.

Here is a summary of the results of this simulation.

1. (31)

   

Not only are the counts the same, but the languages themselves are the same (OT-Help does these calculations and comparisons automatically).

An interesting aspect of this result is that the constraint set contains the gradient Alignment constraints Align(Ft) and Align(Hd), which, as we saw in §6.3, can lead to significant differences in the predictions of OT and HG. Crucially, however, the constraint set contains neither Parse-σ nor Weight-to-Stress. Because it lacks Parse-σ, the trade-off in violations between it and Align(Ft) illustrated in (29) does not exist in the current set of violation profiles. Because it lacks Weight-to-Stress, a trade-off with Align(Hd), discussed by Legendre et al. (Reference Legendre, Sorace, Smolensky, Smolensky and Legendre2006) and Pater (Reference Pater2009b), is also absent. We do not take this as evidence for the elimination of Weight-to-Stress and Parse-σ from metrical theory. Rather, it serves to further illustrate the crucial point that it is the trade-offs between violations of constraints, rather than the way that any one constraint assigns violations, that lead to differences between HG and OT. Like the NoCoda/Max example in the introduction, this is because the version of HG we are considering is an optimisation system.

6.5 Summary

The typological investigations above, which mix qualitative analysis of specific cases with large-scale quantitative assessment, point up the complexity of the relationship between OT and HG. There are constraint sets for which the two frameworks are aligned in their typological predictions, and there are constraint sets for which they diverge wildly. The examples show that certain constraint combinations can have apparent ill-effects in one framework even as they produce desirable patterns in the other. These findings are just small pieces in the larger puzzle of how the two approaches relate to one another. We think the connection with linear programming, and the computational tools that go with it, can facilitate rapid progress in putting the rest of the pieces together.