4.1 Automata

Finite-state automata enjoy almost every imaginable closure and decidability property we might be interested in: ‘an often stated rule of thumb [is] that everything concerning finite automata is decidable’ (Salomaa Reference Salomaa, Rozenberg and Salomaa1993: 572). Automata are closed under all Boolean operations, and other operations such as reversals and homomorphisms; two automata can be tested for equivalence; two automata can be tested to see if one represents a subset of the other; an automaton can be tested for emptiness and universality (whether it accepts all strings over the alphabet). Automata also have a canonical minimal representation, which is efficient to compute (from a deterministic automaton) (Hopcroft Reference Hopcroft1971). Automata can also be constructed from various flavours of regular expression formalisms (Kaplan & Kay Reference Kaplan and Kay1994, Karttunen Reference Karttunen1995, Mohri & Sproat Reference Mohri and Sproat1996, Vaillette Reference Vaillette2004, Yli-Jyrä Reference Yli-Jyrä, Koskenniemi and Holub2007, Hulden Reference Hulden2009a). These are mostly classical results dating back to Moore (Reference Moore, Shannon and McCarthy1956), Myhill (Reference Myhill1957) and Rabin & Scott (Reference Rabin and Scott1959), and most of these properties can also be decided through very efficient algorithms (Hopcroft & Ullman Reference Hopcroft and Ullman1979).

4.2 Transducers

In contrast to finite automata, transducers are more delicate in their properties. Transducers are closed under concatenation and union, but not complementation and intersection, or subtraction. Transducers also cannot, in the general case, be tested for equivalence (Griffiths Reference Griffiths1968) – i.e. the problem is undecidable by algorithm. From the point of view of phonology, these properties imply that in order to perform model checking on transducer implementations of phonological mappings, we must be careful to stay within the bounds of algorithmic capacity. Below, I outline the main stumbling blocks that transducers pose for formal verification, and also point to methods to get around the limitations in most cases.

The first two well-known theorems which I will refer to are given in (1).

1. (1)

   

The consequence of the two theorems is that whenever two phonological mappings or grammars are represented as transducers and at least one of the mappings represents a function (i.e. admits no variation), the two grammars can be tested for equivalence. If this is not the case, equivalence testing may not be available. It should be noted that two grammars that admit variation may very well end up being represented by structurally identical transducers, in which case we can immediately conclude their equivalence. The general problem here is that two mappings may be modelled by two structurally different transducers that still represent the same relation; Fig. 1 gives a simple example.

Figure 1

Two transducers that model the same mapping but are structurally distinct.

Note that in this article, a phonological grammar that produces the same UR/SR mappings as some other grammar with a different alignment of individual input–output symbol pairs will be considered equivalent. In other words, the question of exactly how input–output symbols align in the final UR/SR mapping is ignored.

The theorem in (2) (Blattner & Head Reference Blattner and Head1977, Culik II Reference Culik II1978) tells us, from a phonological point of view, that if a grammar is represented as a transducer, we can decide algorithmically whether it admits alternative outputs.

1. (2)

   

Here it is worth noting that there is no algorithm for separating the ambiguous mappings (i.e. those inputs that admit free variation) from the unambiguous ones (Hulden Reference Hulden2009a). The equivalence of two transducers is thus not decidable, even for those parts that have unambiguous input–output pairs.

However, there is a technically subtle point that is important here: while we cannot separate the ambiguous mappings in a transducer (i.e. x↦{y, z}) from the unambiguous ones (x↦y), we can extract the set of input strings that induce two or more successful paths in a transducer (Hulden Reference Hulden2009a: 150–156), as in (3). Some of those paths may very well result in the same output (i.e. map x↦y with different alignments of symbols). In other words, we cannot disentangle those ambiguous paths in a transducer that actually contain ambiguous mappings from those that do not.Footnote ³ However, if we know a priori from the way a transducer was constructed that every ambiguous input path through the transducer also produces an ambiguous output, we can separate out the parts that induce variation, and perform equivalence testing on those parts that do not – this is indeed the case with most rewrite-rule grammars built through composition of single rules.

1. (3)

   

An important tool in the formal verification of phonological grammars is the ability to extract the set of inputs and outputs from an FST. Since these can be represented as automata, the results of input/output (domain and range) extraction from a relation often allow us to investigate properties of a grammar in greater depth, by virtue of the strong closure and decision properties that automata enjoy.

Many of the above algorithms are available in standard finite-state toolkits like xfst (Beesley & Karttunen Reference Beesley and Karttunen2003) and Kleene (Beesley Reference Beesley2012). In the following, I will assume the use of the foma-toolkit (Hulden Reference Hulden2009b), which contains implementations of all the algorithms discussed in this paper.

4.3 Proofs

Judicious combinations of the above techniques allow us to achieve something very desirable in phonology – formal proof of equivalence between models. Such proofs could be model-internal: one may want to prove that two different OT analyses are equivalent, despite employing different constraints, or prove that two rule-based accounts yield the same results. Alternatively, and probably more commonly, one may want to show equivalence of seemingly different analyses in different formalisms, say a rule-based account and an OT account, or an autosegmental model and a rule-based model. But we need not restrict ourselves to proof of equivalence only. Finite-state techniques also allow us to analyse, in detail, where two superficially dissimilar accounts contrast in their predictions.

5.1 Conspiracies and output goals

An introductory example: an important type of formal analysis is afforded by the ability to represent sequences of rewrite rules as transducers is the ability to verify the presence of generalisations over the output set (Kisseberth Reference Kisseberth1970).

Having at our disposal a transducer which represents an entire grammar directly permits an analysis of the possible outputs of such a transducer. Extracting the range of outputs from a transducer that represents the effect of a rule or multiple rules yields a finite automaton that encodes the implicit surface phonotactics entailed by the rules. As an illustration, consider a simple hiatus-avoiding rule that deletes consecutive vowels, as in (7).

1. (7)

   

By recasting this operation as a regular expression [V→ᴓ // V_].l, we can compile it into an automaton that characterises the set of possible outputs, as in Fig 2.

Figure 2

Automaton encoding all the possible outputs (given any input) of a rule that deletes the latter of two consecutive vowels. The @-symbol represents any symbol except V.

In this case, an inspection of the result is sufficient to establish that the effect of the rule is such as to preclude output configurations that contain VV. We could also establish this formally by calculating the intersection of this language with the language where every string contains a VV sequence somewhere, as in (8).

1. (8)

   

By virtue of this analysis yielding an automaton that represents the empty set, it serves to verify formally that no VV sequences can surface as a consequence of the rule.Footnote ⁴

In the analysis of more complex interactions of rules, the combined effect of multiple rules that conspire to constrain outputs may not be as easy to identify; casting the results as an automaton allows us to directly analyse the potential outputs of a cascade of rules and the indirect ‘goals’ that a battery of rules implicitly defines.

6.1 FST implementations of OT grammars

In the following, I draw on and develop further a technique for converting OT specifications into FSTs introduced by Gerdemann & van Noord (Reference Gerdemann and van Noord2000) and expanded in Gerdemann & Hulden (Reference Gerdemann and Hulden2012); similar approaches can be seen elsewhere (Eisner Reference Eisner2002), and many other finite-state approaches have been proposed (e.g. Ellison Reference Ellison1994, Hammond Reference Hammond1997, Karttunen Reference Karttunen, Karttunen and Oflazer1998, Riggle Reference Riggle2004).

The basic idea is as follows. We first create a Gen-transducer that takes an arbitrary input and modifies it in all the possible ways Gen is assumed to do. An entirely generic Gen would of course arbitrarily insert, delete and epenthesise segments, as well as lay down feet, syllabify, mark stress, etc. Since we later need to identify where constraints are violated, in practice this requires us to preserve the input and keep the output distinct from the input. There are many potential mark-up schemes for doing so, one simple choice being to separate the input and output through mark-up symbols. If, as is the case in all of the concrete grammars presented in this article, we only choose to investigate certain possible deletions, insertions and modifications, it is possible to restrict Gen accordingly. This may be the case when a stress pattern or syllabification is the phenomenon under consideration, and all faithfulness constraints are assumed to outrank markedness constraints for the phenomenon at hand. A Gen-transducer for syllabification, for example, may be designed to only add syllable boundaries to the input arbitrarily. Naturally, it is possible to always work with a maximally generic Gen, at the cost of some complexity. Such a Gen would also require explicit specification of all faithfulness constraints for every grammar.

Having created a Gen-transducer, we can proceed to model the evaluation of constraints, i.e. the Eval component. This is done by composition with successive transducers that remove the suboptimal candidates in the pool for each constraint, i.e. copy the best candidate(s) from input to output and map everything else to the empty set. In the transducer notation presented above, the overall scheme is as in (10).

1. (10)

   

Since transducers have a finite number of states and hence cannot ‘count’ violations without bound, some approximation has to be performed at this step. One possibility is to break down each filtering transducer into a transducer that marks up violations and then removes those candidates with k violations or more, then k®1, etc. This is the approach taken in Karttunen (Reference Karttunen2006b). The downside of such an approach is that it will not produce a transducer that is generic in the sense of being able to produce the correct output for an input of any length with any number of violations. There exists another possibility, however, which is to use the set of candidates to produce worse candidates by an auxiliary transducer, and in turn use that transducer to filter out the suboptimal candidates (Gerdemann & van Noord Reference Gerdemann and van Noord2000). For example, consider a syllabifying Gen-transducer (as in Fig. 3) and a constraint Peak, which requires syllables to have exactly one vowel; assume that Peak is the first constraint to be evaluated. For the input /paka/, the possible outputs of Gen will be [paka, pak.a, pa.ka, pa.k.a, p.aka, p.ak.a, p.a.ka, p.a.k.a].

Figure 3

Example of a simple Gen-transducer for syllabification. The @-symbols represent any symbol outside the alphabet (i.e. symbols mentioned on other transitions here).

Now consider a transducer, W, that performs the mappings in (11) for syllabified words.

1. (11)

   

It can be is easily seen that the set of outputs for this transducer has the following structure: (i) all six suboptimal candidates are in the union of the set of outputs, and (ii) each input maps to only candidates that are strictly worse than the corresponding input. If W fulfils these properties for any syllabified input, then we can use this set of outputs to mimic an Eval-function, as in (12).

1. (12)

   

That is, we compose Gen with the complement of the set of outputs that occur when Gen is composed with the W-transducer. The result of this will be a transducer that always removes the suboptimal candidates from the current pool. This hinges crucially on our ability to create such a transducer for each constraint.

The conditions for being able to express an OT grammar as a transducer can then be summarised as in (13).

1. (13)

   

This is a sufficient condition; whether it is a necessary condition is an open question.Footnote ⁵ More informally, it simply places a restriction on the class of OT grammars that one must be able to describe, by means of a transducer, what the set of worse candidates looks like, given the optimal candidate and some constraint.

A roundabout way of achieving this kind of filter – one that is very convenient for most constraints – is to create it in two steps. First, create a transducer that marks violations of a particular constraint with a symbol, say *, then compose the result with a transducer that adds at least one violation mark to each word, as in (14a), which allows us calculate (14b).

1. (14)

   

The logic is that out of the marked-up violations produced by the Gen .o. Peak transducer, we want to filter out those that would be in the output if we further added at least a violation marker (AddViol) and undoing and redoing Gen's mark-up arbitrarily. We thus indirectly define the worse candidates as those that have the same violation markers as the optimal ones, and some more besides. The reason for Gen's effect being ‘undone’ and ‘redone’ by [Gen.i .o. Gen]/%* is that an optimal candidate, say [pa.ta], will not generate a suboptimal one such as [p*.ata*] by this scheme, because the syllable boundaries do not align in the two. By undoing and redoing Gen's effects arbitrarily we can produce, from [pa.ta], a number of suboptimal candidates, such as [p*.ata*, pata*, p*.a.t*.a]. This approach has the advantage of performing the desired calculation in a generic fashion, and allows us to focus on constructing only a transducer that marks violations with *.

Despite the calculations being somewhat involved, many finite-state toolkits allow one to wrap all of the above into convenient automated macros, freeing the phonologist to simply specify what constitutes a violation, using regular expressions.

In the formalism we are working with, we can define generic macros that perform all the work described above for multiple constraints, as in (15a).

1. (15)

   

Here Eval is a macro that, when given an arbitrary transducer argument X, performs exactly the above calculation, and at the end, removes the temporary violation markers. The action of adding violations is defined through a generic transducer Worsen. For example, if we now had an OT grammar with three constraints and the corresponding transducers that mark up violations of those constraints, say Con1, Con2 and Con3, we could simply calculate the expression in (15b) to produce an FST of the entire grammar. Here Gen may be tailored to the grammar, of course. It is worth noting in particular the recursive use of the Eval macro/function, which is calculated inside out in the expression.

This method allows us – under most circumstances – to convert an OT grammar specification into an FST that models the grammar exactly for all inputs. If the suboptimal candidates always have violation markers in all the same places as some better candidate, the method is implicitly able to distinguish between an unbounded number of violations, despite being finite-state.

Some grammars, however, are going to exhibit cases where the condition on alignments does not hold. Consider a case where only two outputs remain at the point of evaluating a markedness constraint, Stress-to-Weight, which militates against non-heavy stressed syllables. The violation markers would be inserted as in (16).

1. (16)

   

The optimal candidate, (a), will not coincide with the suboptimal one, (b), even after shuffling around the foot markers and adding violations, simply because the violations do not align. As such, the above strategy would fail to distinguish between the two candidates, letting the suboptimal one slip through the finite-state sieve. One way to remedy a situation like this is to add a permutation transducer in the loop that moves violation markers around before adding violations (Gerdemann & van Noord Reference Gerdemann and van Noord2000). It is beyond finite-state power to move symbols around some arbitrary distance, but for many purposes the Eval transducer can be sufficiently strengthened to give it the power to distinguish just enough disparity in violation alignment, as in (17).

1. (17)

   

The Perm transducer (also shown in Fig. 4) moves markers arbitrarily but maximally to the next violation position in the same word.

Figure 4

Illustration of a transducer that ‘permutes’ violation markers. @-symbols repeat everything that is not a *.

For example, given the input (H́.L).L.(H̀.L).(L̀*.H), the Perm transducer would output at least the possibilities in (18).

1. (18)

   

After such a manoeuvre, it is clear that (16a) can be made to coincide with (16b) by undoing and redoing Gen – in this case by refooting and restressing, since the role of Gen in this particular application is to lay down feet and stress syllables.

It is possible, of course, to compose the permutation transducer, Perm, indefinitely with itself multiple times to allow for increasingly stricter alignment matching and better Eval functions. For all practical grammar evaluations I have seen, zero or one round of permutation is sufficient. Where one round is not enough, it is generally the case that the grammar itself is not expressible as an FST.

Fortunately for the grammar designer, it is possible to decide algorithmically whether permutation is needed to avoid suboptimal candidates from slipping though the cracks of Eval. It is also possible to decide when a sufficient number of permutations have been performed. This is based on the fact that (as seen above) we can algorithmically decide when a transducer represents a function. To evaluate whether an Eval filter is sufficient, we can first apply the filter that removes suboptimal candidates, retain the violation markers and compose the result with a transducer Rem that removes everything except the markers, as in (19a).

1. (19)

   

In this example with the candidates in (16), the resulting transducer would perform the mapping in (19b). That is, some input (HLLHLLH in this case) would map to two different outputs. The entire system, therefore, would not represent a function. This circumstance allows us, after each additional permutation, to test whether the resulting transducer, after retaining the markers and composing with Rem, is a function. If so, we can stop permuting. In short, we can detect the necessity of permutation, and also know when the method has produced an exact FST model of the OT grammar at hand which correctly distinguishes between all optimal and suboptimal candidates.

A grammar can plausibly contain a constraint such that no amount of permutation will suffice to achieve an exact model. In most cases this corresponds to a grammar that simply is not finite-state, such as the one in (9) above.

6.2 OT variants

Although not illustrated below with practical examples, it is obvious that many variants of OT, such as derivational and stratal models (Rubach Reference Rubach2000, Bermúdez-Otero Reference Bermúdez-Otero and de Lacy2007) can be profitably implemented, insofar as the individual constraints that they employ can be cast into FST form, as above. This is because of the ability to compose individual FSTs together (each of which presumably represents a level in the overall grammar). Other variants, such as comparative markedness models (McCarthy Reference McCarthy2003), can also be represented, subject to the general caveats that prevail concerning FST modelling.

7.1 Comparison between models: a case study of Finnish prosody

7.1.3 OT models of Finnish word stress

Both Elenbaas (Reference Elenbaas1999) and Kiparsky (Reference Kiparsky, Nelson and Manninen2003) develop OT analyses of Finnish word stress, implemented in Karttunen (Reference Karttunen2006b) as a transducer using a method for approximating OT grammars with transducers (Karttunen Reference Karttunen, Karttunen and Oflazer1998). In what follows, instead of using an approximation (which cannot be universally compared with an exact rule-based transducer), I will implement the same analyses as an exact transducer using the methods described above.

The constraints proposed in Elenbaas (Reference Elenbaas1999) and Kiparsky (Reference Kiparsky, Nelson and Manninen2003) are given in (25), shown in order of ranking, and described together with rewrite rules that indicate how to mark up violations.Footnote ⁷

1. (25)

   

The two constraints (g.i) and (g.ii) reflect the main differences between Kiparsky (Reference Kiparsky, Nelson and Manninen2003) and Elenbaas (Reference Elenbaas1999). I will consider both variants, but initially describe the implementation of (g.i), Stress-to-Weight.

The highest-ranked constraint, MainStress, is considered categorical and inviolable, and there is no need to mark up violations. Instead, we assume that we can simply filter out all candidates that violate it after Gen has marked up feet, syllable boundaries and stresses. The transducer for Gen is built as in (26) (cf. Karttunen Reference Karttunen2006b).

1. (26)

   

The component transducers MarkNonDiphthongs and Syllabify take care of Finnish syllabification, which is not handled by the OT constraints here (although one could do so with constraints ranked higher than those under discussion). Stress arbitrarily marks stress on vowels, and Scan arbitrarily divides words into feet. The very first transducer in the composition, [C|USV]*, simply acts as a filter constraining all inputs to only consist of Finnish consonants or unstressed vowels. For formal comparison, it is important to prevent Gen's mark-up from being allowed in the input and to force the rule-based transducer and the resulting OT transducer to have the same domain. Hence, the Gen-transducer maps the single word [pata] to the outputs in (27).

1. (27)

   

This is a relatively small number of candidates. However, the number grows rapidly with the length of the input word. The longest non-compound word in Finnish is often cited as being epäjärjestelmällistyttämättömyydelläänsäkäänköhän.Footnote ⁸ This input word yields more than 636 trillion candidates, illustrating the need for formal analyses.

From the constraint Clash onward we can proceed to filter out suboptimal candidates with the Eval function developed earlier. It turns out that all of the constraints except Stress-to-Weight can be implemented exactly, without any permutation of violation markers. After one composition with the permutation transducer, Stress-to-Weight becomes exact.

Putting the entire grammar together produces a transducer that has 168 states and 3129 arcs, and exactly represents the OT grammar in question. It assigns a syllabified, footed and stress-marked output for any combination of Finnish characters, no matter how long the input word and no matter how many violations it incurs for some constraint.

Except for the last gradient constraint, AllFeet-L, which is implemented with the function EvalAllFeet-L, the actual expression to compile the grammar using the Eval function is as in (28).

1. (28)

   

Before further analysis, let us return to the point about the uncertainty of exactly capturing gradient constraints raised in §6.1.1. How do we know that the transducer implementation of AllFeet-L indeed manages to filter out all suboptimal candidates, and that none slip through the cracks? As indicated before, this needs to be settled on a case-by-case basis. Let us begin by noting that in this particular ranking the gradient constraint is the last in the sequence of constraints. Now, the final FST can be tested for functionality, i.e. whether every input maps to exactly one output, as discussed in §4. In this case, the resulting FST is functional, and so we know a fortiori that it cannot rank two different candidates equally in the last step.

With two FSTs in hand, Traditional and Kiparsky, we can proceed to test the two for equivalence, as described in §4. The two are not equivalent. This is expected, since the Traditional transducer contains ternary feet of the form (σσσ), which the OT transducer does not. Composing each with a transducer that removes the parentheses marking off feet, they are still not equivalent – which means they assign stress in different ways. In a similar fashion, we can also compile the analysis in Elenbaas (Reference Elenbaas1999), which replaces Stress-to-Weight with the constraint *(L̀H). It also differs from Traditional.

For a formal analysis it is clearly unsatisfactory to simply conclude that two grammars behave differently. One would also like to know precisely for which inputs this happens. The first step toward a deeper analysis is to transform the three transducers, Traditional, Kiparsky and Elenbaas, to produce a more generic output, one that simply outputs sequences of Ls and Hs, with possible stress markings. This can be achieved by composing the stress-marking transducers with a transducer that converts the syllables into sequences over symbols H, H́, L, Ĺ, as in (29a).

1. (29)

   

That is, we simply map all syllables to one-letter descriptions. The resulting FSTs now map word inputs into HL sequences, as in (29b).

The output projections of these transducers are regular languages over four symbols. These can be extracted, producing automata that implicitly encode how the grammars in question assign stress. This is because if, for example, an ĹLLH́HĹL appears in the language, we know that this is how the grammar stresses any LLLHHLL input. I will call the resulting automata TraditionalC, KiparskyC and ElenbaasC. Since we are now dealing with regular languages, i.e. automata as opposed to relations, we are free to use all Boolean operations on the automata. We can, for example, calculate the set of words for which a pair of the three automata give different predictions, say KiparskyC and TraditionalC, as shown in (30).Footnote ⁹

1. (30)

   

We now have an automaton that models all the differences between the two grammars. One useful question to ask is: what is the shortest string where the two differ? This is a simple calculation; there are 32 strings of length 6 with different outputs, one of them being ĹHLĹLL. This corresponds to, for example, the real word *(ˈka.las).te.(ˌle.mi).nen (Kiparsky) and (ˈka.las).(ˌte.le).(ˌmi.nen) (Traditional). Apart from these, there are an infinite number of input patterns where the two grammars give diverging results, as shown in Fig. 5.

Figure 5

An FSA that represents the complete set of input patterns in which the Stress-to-Weight OT analysis (Kiparsky) differs from the traditional one.

To better analyse the differences, it is convenient to collapse the stress distinctions in this ‘difference automaton’, since our primary concern is to see which inputs produce different outputs. Hence we compose DiffKT with a transducer that removes the distinction between Ĺ and L, as well as between H́ and H, as in (31).

1. (31)

   

The result of this is what is seen in Fig. 5, giving a compact overview of the shortcomings of the OT analysis. Figure 6 shows the corresponding differences between TraditionalC and ElenbaasC, i.e. the Elenbaas analysis.

Figure 6

An FSA that represents the complete set of patterns in which the *(L̀H) OT analysis (Elenbaas) differs from the traditional one.

7.2 Partial analyses and internal comparison: Hixkaryana stress

One perhaps troubling aspect about Optimality Theory is the prevalence of partial analyses in the literature.Footnote ¹⁰ These are analyses where only a few constraints are investigated through tableaux, and any candidates not examined are implicitly assumed to be removed by higher-ranked constraints. This makes formal analysis difficult, and any potential errors can only be assumed to be ‘real’ errors if they stem from a miscounting of violations for the candidates that are scrutinised. Any candidate omitted from the discussion can always be chalked up to the effects of a higher-ranked constraint.

The analysis of Hixkaryana stress exemplifies a number of these issues. First, in Kager's (Reference Kager1999) analysis, we find that a number of constraints are simply omitted from the analysis. In particular, these constraints are tacitly assumed to outrank the constraints discussed, and so the analysis proceeds without considering a large number of candidates that under other circumstances would be in contention.

Even so, there are ways to approach such partial analyses. We can attempt to encode the grammar in two ways: with and without the implicit assumptions included. Upon implementation, we find that the constraints give incorrect winners. This result was also arrived at in Halle & Idsardi (Reference Idsardi2000); however, the approach proposed here allows us to verify formally that the analysis is flawed, and also helps in correcting the analysis in a much simpler way than is done in Halle & Idsardi (Reference Idsardi2000).