2.1 Summary of the typology

As was true for earlier researchers, ‘stress pattern’ refers to the dominant stress pattern of the language, and thus the typology ignores lexical exceptions. The typology also does not distinguish stress patterns if they differ only in the domain of their application – e.g. roots vs. phrases or nouns vs. verbs. Also, as is fully explained in §3, stress patterns here are conceived as patterns over strings of syllables, not segments.

Combining Bailey's (Reference Bailey1995) and Gordon's (Reference Gordon2002) stress typologies yields a typology of 422 languages, exhibiting 109 distinct stress patterns, representing over 70 language families.Footnote ⁴

Stress patterns are broadly categorised into three groups by primary stress placement: quantity-insensitive, quantity-sensitive bounded and quantity-sensitive unbounded. Appendix A organises the stress patterns in the typology into these three categories and shows the extensive variation documented in those studies. For the sake of completeness, I briefly review these categories and some of the variation below, though most of the discussion will undoubtedly be familiar to anyone with anything greater than a passing interest in stress patterns. For further details, the reader is referred to Bailey (Reference Bailey1995), Hayes (Reference Hayes1995) and Gordon (Reference Gordon2002), and the primary source references therein. Kager (Reference Kager and de Lacy2007) provides a thorough overview of the different kinds of patterns.

Quantity-insensitive (QI) stress patterns, extensively reviewed in Gordon (Reference Gordon2002), are those in which the statement of the stress rule need not refer to the quantity, or weight, of the syllables. 319 languages in the typology are quantity-insensitive, exhibiting 39 distinct stress patterns. These patterns can be divided into four kinds: single, dual, binary and ternary systems (Gordon Reference Gordon2002). Single stress systems have a single stressed syllable in each word. Dual stress systems have at most two stressed syllables in each word. Binary and ternary systems have no fixed upper bound on the number of stressed syllables in a word and place stress on every second or third syllable respectively. All QI systems are bounded – that is primary stress falls within some window of the word edge. No other kind of QI stress system is attested.

Quantity-sensitive (QS) stress systems are unlike QI stress systems in that stress placement is predictable only if reference is made to syllable types. Because syllable distinctions are usually describable in terms of the quantity, or weight, of a syllable, such patterns are called quantity-sensitive.Footnote ⁵ Bailey's (Reference Bailey1995) typology only describes the placement of primary stress; secondary stress information on each of those languages was collected from primary sources when available.Footnote ⁶ The resulting typology includes 44 patterns which have quantity-sensitive bounded patterns.

Like the QI patterns, QS bounded patterns can be subdivided into single, dual, binary, ternary and ‘multiple’ types (‘multiple’ is defined below). Because of the weight distinction, each of these subtypes shows extensive variation. There are 58 QS bounded languages in the typology, exhibiting 44 stress patterns.

Some languages assign primary stress like the single systems described above, and place secondary stress only on heavy syllables, e.g. Cambodian. These patterns I call ‘multiple’ QS patterns. They are similar to binary and ternary patterns in that there is no clear principled upper limit on how many syllables in a word can receive stress. But they differ from binary and ternary patterns in that any number of unstressed syllables can occur between stresses. They are included here with QS bounded systems because the location of primary stress is bounded.

On the other hand, QS unbounded stress systems place no limits on the distances between primary stress and word edges, as primary stress usually falls on the leftmost (or rightmost) heavy syllable from the left (or right) word edge. These are the four basic groupings, but again variation exists within each of these subgroups. It is the non-local aspect of unbounded patterns which make them challenging for learning proposals. 45 languages with QS unbounded stress systems are in the typology, exhibiting 26 distinct patterns.

2.2 Phonotactic restrictions

In addition to the different stress-assignment rules described below, there is additional variation that is relevant to a learner of stress patterns. Some languages place additional restrictions on which strings of syllables are well-formed. Many languages prohibit monosyllabic words, or words consisting of a single light syllable. Other languages require every word to have at least (or at most) one heavy syllable. These phonotactic constraints matter for a learner, because words which violate these phonotactic constraints are never present in the learner's linguistic environment, not even potentially. Therefore, whenever such a restriction was mentioned in a source, it was noted. These restrictions are included in the typology and contribute to the total number of distinct patterns. For example, Alawa (Sharpe Reference Sharpe1972) and Mohawk (Michelson Reference Michelson1988) both assign stress to the penultimate syllable, but words in Mohawk are minimally disyllabic, which as far as I know is not the case in Alawa, and so both of these patterns, which differ minimally in this respect, are included in the typology as distinct patterns.

2.3 Unattested stress patterns

Despite the extensive variation recounted above, stress patterns are not arbitrary. There are many logically possible ways to assign stress which are unattested. No language places a stress on the fourth syllable from the right (or left) in words of four syllables or longer, and on the first (or final) syllable in words of three syllables or fewer. No stress pattern places stress on every fourth or every fifth syllable (cf. the binary and ternary patterns above which place stress on every second or third syllable).Footnote ⁷ Moving further afield, languages do not place stress on every nth syllable, where n is a prime number, nor on every nth syllable, where n is equal to some prime number minus one. When we consider the myriad of logically possible ways stress can be assigned, the attested variation appears quite constrained. This is not a new observation – virtually every previous researcher essentially makes the same point. I emphasise it only to spotlight the question: what property or properties do the attested patterns share which separates them from these unattested patterns?

3.1 Patterns as sets

A pattern can be represented as a set. All logically possible strings which obey the pattern are in the set, and all the possible strings which do not obey the pattern are not in the set. For example, consider the following two attested stress patterns.

1. (3)

   1. a. Primary stress falls on the initial syllable and there is no secondary stress.

   2. b. Primary stress falls on the final syllable and secondary stress falls on other odd syllables, counting from the right.

Afrikaans (Donaldson Reference Donaldson1993) is an example of language said to have the stress pattern of (3a) and Asmat (Voorhoeve Reference Voorhoeve1965) the stress pattern described in (3b). These patterns are given as sets in (4).

1. (4)

   

Following Chomsky (Reference Chomsky1957), I use the word ‘language’ interchangeably with ‘pattern’ to mean sets like those above.

The linguistic competence of speakers of Afrikaans and Asmat with respect to stress patterns can be characterised by knowledge of sets (4a) and (4b) respectively. For example, these speakers can presumably decide whether a logically possible word obeys the relevant pattern or not. For example, a word represented as obeys the stress pattern of (3b), whereas a word with the representation does not. The decision a speaker makes regarding whether a particular word obeys the pattern is akin to deciding whether that word is in set (4b).

One item of interest about the sets in (4) is that they are infinite. It is therefore not possible to write out these sets in their entirety as a list. Grammars, however, are a finite way of writing an infinite set. There are many grammars that can define the sets above. For example, if we use the perfect grid (Prince Reference Prince1983), have parameters which allows us to align a peak of this grid with the right edge of the word and set the End Rule parameter to Right, we can generate the infinite set in (4b). Different settings of such parameters (along with a parameter which essentially removes secondary stress) generate the stress pattern in (4a). On the other hand, if we adopt parameters which give us disyllabic iambic feet (σ) and foot assignment from the right edge, and set a Head Foot parameter to Right, then it is possible to develop a grammar which generates the same infinite set (4b) above (Hayes Reference Hayes1995). Different settings of these parameters again generate (4a). Additionally, a number of studies show how those sets can be generated in OT with different kinds of constraints (Tesar & Smolensky Reference Tesar and Smolensky2000, Gordon Reference Gordon2002, Hyde Reference Hyde2002).

This paper addresses many of the simple, fundamental questions which arise when we view stress patterns – or any linguistic pattern – as sets. What properties do sets such as the ones in (4) have? What properties set possible stress patterns apart from some of the logically possible but phonologically unnatural stress patterns discussed in §2.3? How can such an infinite set (or a grammar which generates it exactly) be acquired from just finitely many examples? In other words, what inductive principles, in the sense of Popper (Reference Popper1959), allow one to obtain set (4a) from the finite set {, σ, σσ, σσσ}? These last questions have been studied extensively by the grammatical inference community, whose research the learner presented in §6 draws upon. De la Higuera (Reference Higuera2005, in press) provides an excellent introduction to grammatical inference.

3.2 Phonotactic patterns are regular sets

Interestingly, phonotactic patterns like the stress patterns in (4) above are all regular sets. Regular sets are those than can be generated by finite-state acceptors.Footnote ⁸ A finite-state acceptor (FSA) is a grammar which contains a finite number of states, some of which are start states and some of which are final states, along with labelled transitions between those states. A FSA is said to generate a string if and only if there is a path from a start state to a final state which ‘exhausts’ the string.Footnote ⁹ Examples which make this notion clear are given below. There are several excellent introductions to finite-state acceptors, including Partee et al. (Reference Partee, Meulen and Wall1990), Sipser (Reference Sipser1997), Hopcroft et al. (Reference Hopcroft, Motwani and Ullman2001) and Coleman (Reference Coleman2005), to which I refer readers. The focus on finite-state representations here follows earlier work in phonology (Johnson Reference Johnson1972, Koskenniemi Reference Koskenniemi1983, Ellison Reference Ellison1992, Kaplan & Kay Reference Kaplan and Kay1994, Eisner Reference Eisner1997b, Frank & Satta Reference Frank and Satta1998, Karttunen Reference Karttunen1998, Riggle Reference Riggle2004, Albro Reference Albro2005).

As examples, consider the FSAs in Fig. 1, which I call FSA Afrikaans (a) and FSA Asmat (b). In the finite-state diagrams in this paper, start states are indicated by hexagons, and final states by circles with double lines, unless mentioned otherwise. The numbers which label the states are irrelevant to the process of generating strings; they are just names of the states to facilitate discussion. FSA Afrikaans generates the string σσ. This can be seen by checking whether there is path through the machine that begins at a start state and ends at a final state, along transitions that exhaust σσ. FSA Afrikaans is a very simple machine, so it is easy to see that such a path exists. Beginning at state 0, a start state, we travel on the arc labelled to state 1. Then we travel along the arc labelled σ, which brings us back to state 1. We traverse this arc again returning to state 1 one more time. At this point we have exhausted the string and, since state 1 is a final state, there is in fact a path from a start state to a final state which exhausts the string. FSA Afrikaans does not accept the string σσ, because there is no start state that has a transition leaving it which is labelled σ. It is easy to see that FSA Afrikaans accepts all and only those strings that begin with followed by zero or more σ. Although FSA Asmat is more complex, in the sense that there are more states and arcs, it is also straightforward to see that the only strings it accepts are the ones which obey the stress pattern of Asmat in (3b).

Figure 1

The stress patterns of (a) Afrikaans and (b) Asmat.

FSAs Afrikaans and Asmat are faithful representations of the stress patterns in (3), because they generate exactly the sets in (4). Like the generative grammars of earlier researchers, these grammars recognise infinitely many well-formed words. FSAs are categorical phonotactic grammars, because they are devices that can answer yes or no when asked if some logically possible word is possible, which is the minimum requirement of a phonotactic grammar (Chomsky & Halle Reference Chomsky and Halle1965, Reference Chomsky and Halle1968, Halle Reference Halle, Halle, Bresnan and Miller1978). Stress patterns are usually described as categorical patterns, as opposed to gradient ones, although notice that gradient phonotactic patterns can be described with weighted FSAs.Footnote ¹⁰

In fact, the hypothesis that all phonotactic patterns – not just stress patterns – are regular is well supported.Footnote ¹¹ The general form of the argument begins with recognising that phonological alternations can be described as relations. A relation is simply a set of pairs. An underlying form u surfaces as a phonological string s and thus can be written as the pair (u, s). The set of such pairs for a language constitutes the phonological alternations in the language. In the same way that sets can be classified according to their complexity, so can relations. For example, regular relations are those recognised by finite-state transducers. A finite-state transducer is like an acceptor, except the transitions on the labels are pairs of symbols. Since the righthand side of a regular relation – the set of surface forms s – is a regular set (Sipser Reference Sipser1997, Hopcroft et al. Reference Hopcroft, Motwani and Ullman2001), it follows that if all phonological processes which map underlying forms to surface forms can be described with regular relations then all phonotactic patterns are regular sets.

This argument is made by Johnson (Reference Johnson1972) and Kaplan & Kay (Reference Kaplan and Kay1994), who show how to construct a finite-state transducer from traditional SPE-style ordered rule-based phonological grammars (see also Koskenniemi Reference Koskenniemi1983). Similarly, Gerdemann & van Noord (Reference Gerdemann, van Noord, Eisner, Karttunen and Thériault2000) and Riggle (Reference Riggle2004), building on work by Ellison (Reference Ellison1994), Eisner (Reference Eisner1997b), Frank & Satta (Reference Frank and Satta1998), Karttunen (Reference Karttunen1998) and Albro (Reference Albro2005), show how to construct a finite-state transducer from OT grammars, provided the constraints in Con can be written as vector-weighted finite-state transducers.

For example, consider the (different) OT analyses given in Tesar (Reference Tesar1998) and Gordon (Reference Gordon2002) of the stress pattern of Asmat (3b). If these analyses were encoded in finite-state OT, applying Gerdemann & van Noord's (Reference Gerdemann, van Noord, Eisner, Karttunen and Thériault2000) or Riggle's (Reference Riggle2004) transducer-construction algorithm would yield the (same) acceptor shown above in Fig. 1.Footnote ¹² In a sense, FSA Asmat (Fig. 1a) implicitly embodies all the constraints and the rankings used in those analyses (and all the parameters and their settings in a P&P analysis, as well as all the rules and orderings in a derivational analysis). This seems to imply that FSAs can serve as a lingua franca between derivational, P&P and OT approaches to phonology.

There are two other reasons to be interested in the hypothesis that all phonotactic patterns are regular. First, the grammatical inference community has developed a considerable literature on learning regular sets. For example, the class of regular languages is not Gold-learnable from positive data (Gold Reference Gold1967, Angluin Reference Angluin1980), but certain subsets of it are (Angluin Reference Angluin1982, Muggleton Reference Muggleton1990, Denis et al. Reference Denis, Lemay, Terlutte, Adriaans, Fernau and van Zaanen2002, Fernau Reference Fernau2003) (Gold-learnability is explained in more detail in §6). Thus it becomes possible to ask: what subset of the regular languages delimits the class of possible phonotactic patterns and do the properties of this class provide inductive principles for learners? Hypotheses (1) and (2) are essentially one answer to this question.

Second, insights made with respect to regular sets can be extended if it is determined that more complex types of grammars are needed. For example, Albro (Reference Albro2005) makes restricted extensions to a finite-state system in order to handle reduplication (see also Roark & Sproat Reference Roark and Sproat2007 for a finite-state approach to reduplication). Also, if the working assumption that phonotactic constraints are categorical is relaxed, finite-state automata whose transitions are labelled with real-valued weights (i.e. stochastic or probabilistic FSAs) are a natural extension, in which gradient well-formedness patterns can be described.

3.3 QS patterns

The patterns of Afrikaans and Asmat above are QI patterns. QS stress patterns can be represented with FSAs as well. For example, consider the unbounded stress pattern ‘leftmost heavy, otherwise rightmost’ in (5).

1. (5) Place stress on the leftmost heavy syllable in the word. If there are no heavy syllables, stress the rightmost syllable.

(6) shows all strings with four syllables or fewer which obey the pattern in (5). Fig. 2 shows a finite-state acceptor which represents this pattern. Again, it is worthwhile to take a moment to verify that the acceptor in Fig. 2 accepts only those strings which obey the pattern in (5) and rejects all strings which do not obey it.

1. (6) Words of four or fewer syllables which obey the ‘leftmost heavy, otherwise rightmost’ stress pattern

   

The set of symbols on the transitions in the acceptor in Fig. 2 is not the same as the one in Fig. 1. This set of symbols is referred to as the alphabet. There are some important issues regarding the choice of alphabet. To avoid a loss of continuity, this discussion is postponed until §6, where it becomes relevant.

Figure 2

The ‘leftmost heavy, otherwise rightmost’ stress pattern.

To sum up this section, it has been established that phonotactic patterns such as stress patterns can be represented faithfully with finite-state acceptors.

4.1 Locality in phonology

It is generally agreed that locality is an important feature of phonological grammars. McCarthy & Prince (Reference McCarthy and Prince1986: 1) write: ‘Consider first the role of counting in grammar. How long may a count run? General considerations of locality … suggest that the answer is probably ‘up to two’: a rule may fix on one specified element and examine a structurally adjacent element and no other'. Similarly, Kenstowicz (Reference Kenstowicz1994: 597) refers to ‘the well-established generalization that linguistic rules do not count beyond two’.

Within the particular domain of stress, the thinking is no different. Halle & Vergnaud (Reference Halle and Vergnaud1987: ix) note that ‘it was felt that phonological processes are essentially local and that all cases of nonlocality should derive from universal properties of rule application’. Hayes (Reference Hayes1995: 34) writes: ‘metrical theory forms part of a general research program to define the ways in which phonological rules may apply non-locally by characterizing such rules as local with respect to a particular representation’.

Focusing exclusively on the role of locality does not mean other factors are unimportant or irrelevant to systems of stress. There are two reasons for the attention given to it here: (i) to see in precisely what way the stress patterns in the typology of stress are local, and (ii) to obtain a clear understanding of the contribution this a priori notion of locality can make to learning.

4.2 Definition of the neighbourhood

The concept ‘neighbourhood’ aims to capture the insight that phonological environments are defined locally, while ‘distinct’ aims to capture the notion that these environments are unique. The main idea is that each state in a finite-state acceptor represents a phonological environment the grammar must be sensitive to. For example in Fig. 1a, state 0 of FSA Afrikaans represents the environment at the beginning of a word, and state 1 represents every other environment (for some related discussion, see Riggle Reference Riggle2004). These two classes of environments are the ones any grammar generating the initial stress pattern of Afrikaans must be sensitive to.

Given the idea that phonological environments are ‘local’, we identify each state with its local characteristics. Thus the neighbourhood of a state is defined as in (7) (to be revised).

1. (7)

   1. a. the set of incoming symbols to the state

   2. b. the set of outgoing symbols from the state

   3. c. whether it is a final state or not

   4. d. whether it is a start state or not

The neighbourhood of a state can be determined by looking solely at whether or not it is final, whether or not it is a start state, the set of symbols coming into the state and the set of symbols departing the state. Pictorially, all the information about the neighbourhood of a state is found within the state itself, as well as the transitions going into and out of that state. For example, suppose states p and q in Fig. 3 belong to some larger acceptor. We can decide that states p and q have the same neighbourhood because they are both non-final, non-start states, and both can be reached by some element of {a, b}, and both can only be exited by observing a member of {c, d}.

Figure 3

Two states with the same neighbourhood.

The size of the neighbourhood can be parameterised by adjusting parts (a) and (b) of the definition in (7). Instead of referring not just to incoming and outgoing symbols – which are really just paths of length one – those definitions can refer to incoming and outgoing paths of lengths j and k respectively. I call a path of length k a k-path. Thus we define the j-k neighbourhood as in (8).

1. (8)

   1. a. the set of incoming j-paths to the state

   2. b. the set of outgoing k-paths from the state

   3. c. whether it is a final state or not

   4. d. whether it is a start state or not

It is now possible to define acceptors that are j-k neighbourhood-distinct.

1. (9) An acceptor is said to be j-k neighbourhood-distinct iff no two states have the same j-k neighbourhood.Footnote ¹³

The class of neighbourhood-distinct languages is defined in (10).

1. (10) The j-k neighbourhood-distinct languages are those for which there is an acceptor which is j-k neighbourhood-distinct.

When the values of j and k are understood from context, I just write neighbourhood-distinct.

For example, FSA Asmat is 1-1 neighbourhood-distinct. This can be determined by listing the neighbourhood of each state and checking to make sure that each neighbourhood is unique. Table I shows the neighbourhoods of each state in FSA Asmat; no neighbourhood is repeated twice.

Table I

The 1-1 neighbourhoods of FSA Asmat in Fig. 1b.

Examples of non-neighbourhood-distinct patterns are given by logically possible unattested stress patterns such as those which place stress on every fourth, fifth, sixth or nth syllable, which are not 1-1 neighbourhood-distinct. To see why, consider the acceptor in Fig. 4, which generates the logically possible stress pattern which assigns stress to the initial syllable and then secondary stress to every fourth syllable.

Figure 4

The FSA for a quaternary stress pattern.

This acceptor generates the strings in (11).

1. (11)

   

In the acceptor in Fig. 4, states 2 and 3 have the same neighbourhood. It is not possible to write some other acceptor for this language that would not have two states like states 2 and 3 above with the same neighbourhood (because the pattern requires exactly three unstressed syllables between stresses). In contrast, the ternary pattern of Iowoy-Oto, for example, which stresses the peninitial syllable and every third syllable afterwards as shown in (11), is neighbourhood-distinct, as can be easily verified from Fig. 5.

1. (12)

   

Figure 5

The FSA for the stress pattern of Ioway-Oto.

Generally speaking, neighbourhood-distinctness characterises a locality condition, which is shared by binary and ternary patterns, but not quaternary patterns or higher n-ary patterns. In §§4.5–4.6 below, I establish that almost all stress patterns, including the long-distance unbounded types, are neighbourhood-distinct. But first, there is some technical ground to cover.

4.3 Neighbourhood-distinct acceptors and languages

Neighbourhood-distinct languages are defined as those that can be generated by neighbourhood-distinct acceptors. However, many different acceptors can recognise exactly the same language, and it is useful to distinguish certain types of acceptors.

For example, Fig. 6 shows another acceptor which represents exactly the stress pattern of Asmat (3b) (the reader can verify that this is true). Like FSA Asmat (Fig. 1), the acceptor in Fig. 6 has a path from a start state to a final state which exhausts the string for any string which obeys the Asmat pattern. What makes this acceptor unlike FSA Asmat is that there are two start states, and so the acceptor is said to be non-deterministic, because when determining whether the acceptor recognises a particular string there is a choice of which state to begin with.

Figure 6

A head canonical acceptor for the stress pattern of Asmat.

Although there are many acceptors which generate a particular set, some are more useful than others. An acceptor like FSA Asmat in Fig. 1b is forward deterministic. This means it has one start state, and for each state q in the machine and each symbol a in the alphabet, there is at most one transition labelled a departing q. A forward deterministic acceptor with the fewest states for a language is called the language's tail canonical acceptor, and typically regular patterns are represented with this acceptor. However, another algebraically equivalent choice is the head canonical acceptor (Heinz Reference Heinz2007). The head canonical acceptor is the smallest reverse deterministic acceptor recognising some pattern. An acceptor is reverse deterministic if and only if there is at most one final state, and for every state q in the acceptor and each symbol a in the alphabet, there is at most one transition labelled a entering q. The acceptor in Fig. 6 is a head canonical acceptor for the pattern in (3b) (the reader may verify that it is reverse deterministic). The tail and head canonical acceptors can be computed from any acceptor which recognises a given pattern (Hopcroft et al. Reference Hopcroft, Motwani and Ullman2001).

The head canonical acceptor for the Asmat pattern is more compact than the tail canonical acceptor, as it has one fewer state and fewer transitions. This is probably due to the fact that it is a right-edge based pattern. Generally, right-edge based stress patterns have smaller head canonical acceptors, whereas left-edge based stress patterns have smaller tail canonical acceptors. This is an interesting observation, which becomes relevant in §8.

I refer to tail canonical acceptors which are j-k neighbourhood-distinct (and the languages they recognise) as tail-canonicallyj-k neighbourhood-distinct. It is useful to refer to head canonical acceptors which are neighbourhood-distinct (and the languages they recognise) as j-k head-canonically neighbourhood-distinct. Finally, I refer to patterns which are either tail or head canonically neighbourhood distinct simply as j-k canonically neighbourhood-distinct. These notions will become useful in §4.5.

4.4 Properties of neighbourhood-distinct languages

An analysis of neighbourhood-distinct languages based on its component parts is begun in Heinz (Reference Heinz2007, Reference Heinz, Clark, Coste and Miclet2008). The results so far show that the class is finite, that the j-k neighbourhood-distinct languages form a structured hierarchy of classes and that it does not have certain closure properties. These are discussed in turn.

1-1 neighbourhood-distinctness is restrictive. The neighbourhood-distinct languages not only form a proper subset of the regular languages over some alphabet Σ, there are only a finite number of them: all regular languages whose smallest acceptors have more than 2²|^Σ|+¹ states cannot be 1-1 neighbourhood-distinct (since at least two states would have the same neighbourhood). Thus most regular languages are not 1-1 neighbourhood-distinct.Footnote ¹⁴

Also, it is obvious that if a pattern is j-k neighbourhood-distinct then it is j′-k′ neighbourhood-distinct when the j′-k′ neighbourhood is larger (i.e. where j′≥j+1 or for some k′≥k+1). Thus neighbourhood-distinct languages form a hierarchy, with language expressiveness increasing as one moves up the hierarchy.

Finally, Heinz (Reference Heinz2007: ch. 6) shows that the j-k neighbourhood-distinct languages are not closed under union, intersection or complement. A language class is said to be closed with respect to some operation if application of the operation to one (or more) languages in the class always yields another language in the class. Since languages here are conceived as sets of strings, union, intersection and complement have their usual meanings. The absence of these properties – in particular intersection – matters, as we will see below.

4.5 Universality

For each of the distinct patterns in the typology, I constructed a finite-state acceptor such that only those words which obey the language's stress rules are recognised by the acceptor.Footnote ¹⁵

In the typology of stress patterns, 97 patterns are tail-canonically 1-1 neighbourhood-distinct and 105 are head-canonically 1-1 neighbourhood distinct. Only two languages are neither tail- nor head-canonically 1-1 neighbourhood-distinct (though they are canonically 2-2 neighbourhood-distinct). In other words, 107 of the 109 types of languages in the stress typology are canonically 1-1 neighbourhood-distinct. One of these two non-canonically 1-1 neighbourhood-distinct stress patterns is provably not 1-1 neighbourhood distinct, the pattern of Içuã Tupi (Abrahamson Reference Abrahamson1968). It remains an open question whether there is some neighbourhood-distinct acceptor which recognises the other one, which is the pattern of Hindi as described by Kelkar (Reference Kelkar1968). Nevertheless, canonical 1-1 neighbourhood-distinctness is a near-universal property of attested stress patterns, and every attested stress pattern is canonically 2-2 neighbourhood-distinct.

To sum up, with two controversial (see below) exceptions, 1-1 neighbourhood-distinctness is a universal property of attested stress patterns. It unites the attested single, dual, binary, ternary and unbounded properties, to the exclusion of quaternary and higher n-ary patterns.

6.1 The learning framework

It is useful to make the learning framework, schematised in Fig. 8, explicit. The idea is that the target language is generated from some grammar G. The learner, however, does not hear every word of the language (as it is infinite in size), but only some small finite sample. The learner is a function which maps finite samples to grammars. The central question we are interested in is: what is the learner such that the Language of G′=Language of G? The paradigm schematised in Fig. 8 is known as exact identification in the limit from positive data (Gold Reference Gold1967). A learner successfully learns language L if, upon being presented with ever larger finite samples from L, the grammars returned by the learning function converge to one which generates exactly L. The class of languages for which a learner can do this is said to be identifiable in the limit from positive data. Nowak et al. (Reference Nowak, Komarova and Niyogi2002) provide an accessible overview of this learning framework and de la Higuera (in press) provides an excellent in-depth introduction to this learning framework and others (see Jain et al. Reference Jain, Osherson, Royer and Sharma1999 and Niyogi Reference Niyogi2006 for more detailed presentations).

Figure 8

The learning framework.

One key result in framing the learning problem this way is that it is known that learning cannot take place unless the hypothesis space is restricted (Gold Reference Gold1967, Angluin Reference Angluin1980). In particular, no learner can identify the class of all regular languages in the limit from positive data.Footnote ¹⁷ This result holds even though learners (i) are given only clean, non-noisy learning data and (ii) may take up as much time or space as they like before returning a hypothesised grammar. The utility of a framework that makes these choices is it focuses the problem squarely on generalisation and whether proposed inductive principles allow one to generalise in the desired ways at all. The fact that, despite the generous conditions learners are allowed to operate under, no learner can learn an unrestricted hypothesis space from positive data makes us confront the problem of generalisation directly.

It follows that for learning to be able to take place at all, G′ is not drawn from an unrestricted set of possible grammars. The hypotheses available to the learner ultimately determine the kinds of generalisations made and the range of possible natural language patterns. Under this perspective, UG is this set of available hypotheses.

Given that neighbourhood-distinct patterns are a restricted class of languages, it is natural to ask whether there is any learning function which can learn them. Because there are only finitely many neighbourhood-distinct languages (see §4.4), there are actually very many learning functions which can identify this class of patterns in the limit (Jain et al. Reference Jain, Osherson, Royer and Sharma1999). However, many of these learners are uninteresting because they make no use of any property of the language class beyond its finiteness.

Therefore, we are interested in a learner for this particular hypothesis space. We might conceive of the learner as making use of the properties defining the space, or more boldly, we might conceive of the properties of the hypothesis space as a consequence of the way the learner works. The Forward Backward Neighbourhood Learner presented below is such a learner, because it generalises to neighbourhood-distinct patterns by its inability to distinguish same-neighbourhood states. Note that to the extent this learner succeeds, it explains why stress patterns are neighbourhood-distinct.

6.2 Overview of the proposed learner

Here I introduce a simple learner which only uses the concept of neighbourhood to generalise. The idea is to merge same-neighbourhood states in the finite-state representation of the input (cf. Angluin Reference Angluin1982, Oncina et al. Reference Oncina, García and Vidal1993). In particular the algorithm is one instantiation of a general algorithm given by Muggleton (Reference Muggleton1990: ch. 6), who provides an accessible introduction to algorithms of this sort (see also de la Higuera, in press: chs 4, 11). As it turns out, this learner does not identify the class of neighbourhood-distinct patterns in the limit, though it does succeed for most of the attested patterns. Code to run the learner is available from the author's website (see note 15).

For ease of exposition, I introduce the learner in two steps. The first step introduces the Forward Neighbourhood Learner, which succeeds on many, but not all, of the attested patterns. I argue that analysis of the languages which the Forward Neighbourhood Learner fails to learn reveals that it is handicapped by the choice of representation of the input. In the second step, I propose an additional alternative representation of the input and a revised learner, the Forward Backward Neighbourhood Learner, which succeeds on many more (but not all) of the attested patterns.

6.3 Prefix trees

A prefix tree is a structured finite-state representation of a finite sample. The idea is that each state in the tree corresponds to a unique prefix in the sample. Here ‘prefix’ is not used in the morphological sense of the word, but rather in a mathematical sense meaning ‘initial sequence’. Constructing a prefix tree is a standard algorithm (Angluin Reference Angluin1982, Muggleton Reference Muggleton1990). Basically, one can imagine building the tree one word at a time, following an existing path in the tree for as long as possible, and then making a new branch as needed.

For example, consider Fig. 9, which shows two prefix trees. The tree in Fig. 9a is a finite-state representation of linguistic experience consisting of all words up to length three syllables. If we add the word σσσ to this finite sample, we obtain the tree in Fig. 9b.

Figure 9

Prefix trees generated by words from the initial stress pattern. (a) PT accepting {, σ, σσ; (b) PT accepting {, σ, σσ, σσσ}.

Figure 10 shows the prefix tree constructed from words up to eight syllables in length from the Asmat pattern.

Figure 10

Prefix tree for Asmat words of eight syllables or fewer.

The prefix tree accepts only the finitely many forms that have been observed. There has been no generalisation at this point. These simple examples show that there is structure in the prefix trees and this structure repeats itself. State-merging, described below, can eliminate this redundant structure, possibly leading to generalisation.

I denote the function which maps some finite sample S to a prefix tree PT, which accepts exactly S with PT. Note that PT(S) can be computed efficiently in the size of the sample S (Angluin Reference Angluin1982, Muggleton Reference Muggleton1990).

6.4 State-merging as a generalisation strategy

The next stage is to generalise by merging states in the prefix tree, a process where two states are identified as equivalent and then merged (i.e. combined). One key concept behind state-merging is that transitions are preserved. Another is that if a final (or start) state is merged with a non-final (or non-start) state, then the merged state is final (or start) (Angluin Reference Angluin1982, Muggleton Reference Muggleton1990, Hopcroft et al. Reference Hopcroft, Motwani and Ullman2001). Generalisations may therefore occur as a consequence of state-merging – because the post-merged machine accepts everything the pre-merged machine accepts, and possibly more.

For example, in Fig. 11 Machine B is the machine obtained by merging states 2 and 3 in Machine A. It is necessary to preserve the transitions in Machine A in Machine B. In particular, there must be a transition from state 2 to state 3 in Machine B. There is such a transition, but because states 2 and 3 are the same state the transition is now a loop. Whereas Machine A only accepts only four words {, σ, σσ, σσσ}, Machine B accepts an infinite number of words {, σ, σσ, σσσ, σσσσ, …}.

Figure 11

An example of generalisation by state-merging. (a) Machine A; (b) Machine B.

The machines in Fig. 11 are familiar. Machine A is the prefix tree in Fig. 9b and Machine B generates the same language as FSA Afrikaans in Fig. 1a. Note that states 2 and 3 are the only states with the same neighbourhood in Machine A, and these are the states that are merged. This is the central insight that the learner below makes use of: merging same-neighbourhood states in a structured representation of the input can result in a correct generalisation.

The merging process itself does not specify which states should be merged. It only specifies a mechanism for determining a new machine once it has been decided which states are to be merged. If other states had been merged in Machine A in Fig. 11, e.g. states 0 and 4, a different (in this case, incorrect) generalisation would have been made. If all states are merged, the result is a one-state machine, with all transitions self-looping to this state. This machine accepts any string of symbols, indicating a massive overgeneralisation. Thus, choosing which states are to be merged determines the kinds of generalisations that occur (Muggleton Reference Muggleton1990, Heinz Reference Heinz, Clark, Coste and Miclet2008).Footnote ¹⁸ A merging strategy is thus a generalisation strategy. It is an inductive principle, in the sense of Popper (Reference Popper1959).

There is one key result regarding state-merging: given any canonical acceptor A for any regular language L and a sufficient sample S of L – that is, a sample which exercises every transition in A – there is some way to merge states in the prefix tree of S which returns acceptor A (Angluin Reference Angluin1982). This result does not tell us how to merge the states for a particular acceptor; it just says that such a way exists. Nonetheless, the result is important because it leaves open the possibility that natural language patterns which form proper subsets of the regular languages (such as stress patterns) can be learned with a state-merging strategy.

6.5 The Forward Neighbourhood Learner

The Forward Neighbourhood Learner (FL) merges states in the prefix tree which have the same 1-1 neighbourhood. I use M _nd to denote the function which maps an acceptor A to the neighbourhood-distinct acceptor obtained by merging all states in A with the same 1-1 neighbourhood. Note that computing M _nd is efficient in the size of A. This is because (i) merging two states is efficient (Hopcroft et al. Reference Hopcroft, Motwani and Ullman2001), (ii) at most all pairs of distinct states need be checked for neighbourhood-equivalence to determine if they should be merged and (iii) determining the neighbourhood-equivalence of two states is efficient. It is now possible to state the Forward Neighbourhood Learner precisely.

1. (13) Algorithm 1: The Forward Neighbourhood Learner

   Input: a positive sample S

   Output: an acceptor A

   Let A=M_nd(PT(S)) and output acceptor A

Figure 11 showed one example of how merging same-neighbourhood states in a prefix tree can lead to successful generalisation. Adding additional words to the prefix tree does not change this result, as the additional states add no new neighbourhoods. Figure 12 shows the result of applying the Forward Learner to the Asmat prefix tree in Fig. 10.

Figure 12

The acceptor obtained by merging same-neighbourhood states in Fig. 10.

This machine accepts the same language as FSA Asmat, though it is not exactly the same machine. In general, the acceptors obtained by the Forward Learner are not necessarily the same as the tail canonical acceptors, nor are they even deterministic. Machine B in Fig. 11 has a source of non-determinism at state 2–3, and the machine in Fig. 12 has a source at 4-7-10-13-19.

However what matters is whether the languages generated by the acceptors are the same as the target patterns. In both examples above, the obtained acceptors do generate the target languages exactly. This can be easily seen by recognising that it is possible to transform these acceptors to the tail canonical ones without adding or losing words to the languages they recognise. In Machine B, for example, state 4 (and its associated transition) can be removed. In Fig. 12, state 17-20 can be removed, along with the transitions associated with it.

6.6 Evaluating the learners

Because the learners in this paper are described in automata-theoretic terms, it is possible that future work will provide proven theorems characterising exactly their behaviour (see Heinz Reference Heinz, Clark, Coste and Miclet2008 for the beginning of such an analysis). But since those characterisations are presently unknown, the proposed learners, such as the Forward Learner above, are evaluated in simulations in the following manner. The input samples presented to the learner consist of all words from one to n syllables which obey the stress pattern.Footnote ¹⁹ Such a sample is referred to as a sample of size n. If the acceptor returned by the algorithm did not accept exactly the same language as the target pattern, this was considered a failure. In such cases, the learner was applied to a sample of size n+1. If the learning did not occur with samples of size nine, or in some cases eight, I concluded there was no input sample with which the learner would succeed. Note that simulations show if the learner succeeded for some input sample of size n, then it also succeeded for sample of size m, where 9>m>n. I take this to mean that, for the kinds of samples provided, the learner converges when given the smaller sample of size n.

Learners were only given words which made the necessary syllable distinctions. For example, QI systems were not given syllables coded for light and heavy, but QS systems which distinguished between syllables of these types were. For example, Table III in Appendix A (see Footnote note 3) shows that the Forward Backward Neighbourhood Learner succeeds in learning the stress pattern of Amele when provided a sample which consisted of all possible words with one to five syllables. Because this language distinguishes light from heavy syllables, there are 2¹+2²+2³+2⁴+2⁵=62 word types in the sample in the simulation.

Although this suggests that the learner's success depends on ‘knowing’ the weight distinction beforehand, this is not so. The choice of alphabet makes the simulation faster to run on a computer, but does not change the nature of the problem. To see why, consider the initial stress pattern in Fig. 1, where the alphabet consists of {, σ}. Suppose we changed the alphabet to include the following symbols {V, CV, CVC, CVV, , C, CC, CV}. The machine would now look like the one in Fig. 13.

Figure 13

The initial stress pattern with multiple syllable types.

The first thing to notice is that changing the alphabet like this does not change the character of the neighbourhoods in the target grammars. This is important, because the learners operate only on the basis of what distinguishes neighbourhoods. Therefore, with such an alphabet, the learners in fact return a machine like the one in Fig. 13. Thus it is fair to say that the learners discover that the distinctions between the syllable types are irrelevant.

It is true that as the alphabet gets larger, the size of the sample also becomes larger. For example, if we use the four-way syllable distinction above, there would be 4¹+4²+4³+4⁴+4⁵=1364 word types in a sample consisting of all words from one to five syllables. Given that what counts as a heavy or light syllable varies across languages, an alphabet which includes every distinction made in any language may get quite large. As the syllable inventory gets larger, so does the concern whether the size of the sample is reasonable, i.e. likely to be present in the lexicon available to a child. This issue is a matter of future research, since it is separate from whether the learners here can be said to discover whether the target pattern is QI or QS when given an alphabet which does not make the distinction overtly.

With these evaluation procedures explained, it can be stated that the Forward Learner successfully learns 85 of the 109 pattern types, as shown in Appendix A.

6.7 Interpreting the results of the Forward Learner

These results also show that the languages in the range of the learning function are not the same as the neighbourhood-distinct languages. The two classes of languages clearly overlap, but the Forward Learner does not identify the class of neighbourhood-distinct languages in the limit. The Forward Learner does not even identify the tail-canonically neighbourhood-distinct languages, falsifying the conjecture of Heinz (Reference Heinz, Wicentowski and Kondark2006) that it does. Nonetheless, the results are promising, because the languages for which the Forward Learner succeeds cross-cuts the QI, QS bounded and QS unbounded stress patterns, suggesting the learner is on the right track.Footnote ²⁰

When we examine the languages which the Forward Learner fails to learn we find that the error is always one of overgeneralisation. This happens because states are merged which should be kept distinct. Consequently, the grammar returned by the learner accepts a language strictly larger than the target language. This means that there is some word for which the learner's grammar accepts different stress assignments. This can be construed as optionality – a particular string of syllables can be stressed in one way or another.

For example, the dual stress pattern of Lower Sorbian requires words with four or more syllables to place primary stress initially, and secondary stress on the penult (e.g. σσ). However, the Forward Learner returns an acceptor which can stress such words in one of two ways: either the same as the target pattern or by placing primary stress on the initial syllable and having no secondary stress at all (e.g. both σσ and σσσ are generated). The reader is referred to Heinz (Reference Heinz, Wicentowski and Kondark2006) for details.

Another characteristic that all stress patterns for which the Forward Learner fails (except Kashmiri) share is that they are typically analysed with a metrical unit at the right word edge.Footnote ²¹ Why would such languages be problematic for the Forward Learner? One idea is that the prefix tree's inherent left-right bias fails to distinguish the necessary states, and this occurs more commonly in languages analysable with a metrical unit at the right word edge. If this were the case, the problem is not with the generalisation procedure per se, but rather with the inherent left-right bias of the prefix tree. Below I propose another way the input to the learner can be represented as a finite-state acceptor: suffix trees.

6.8 Suffix trees

If the input were represented with a suffix tree, then the structure obtained has the reverse bias, a right-to-left bias. Like a prefix tree, a suffix tree is a finite-state representation of the input: it accepts exactly the words from which it was built and nothing else. A suffix tree is structured differently from a prefix tree, however, because each state now represents a unique suffix in the sample instead of a prefix. Whereas a prefix tree is forward-deterministic, a suffix tree is reverse-deterministic. A suffix tree can be constructed in terms of a prefix tree, given some sample. This procedure runs as follows. Given a sample of words, build a prefix tree reading each word in reverse. Since the resulting prefix tree accepts exactly the reverse of each word in the sample, reverse this tree by changing all final states to start states and all start states to final states, and changing the direction of each transition. The resulting acceptor is a suffix tree, and accepts exactly the words in the sample.

Figure 14 shows the suffix tree for the words with eight or fewer syllables which obey the stress pattern of Asmat.

Figure 14

Suffix tree for Asmat words of eight syllables or fewer.

The structure of the suffix tree of this representation is very different from the structure in the prefix tree shown in Fig. 10. Yet both accept exactly the same (finite) set of words. Because they have different structures, the states in a suffix tree may have different neighbourhoods than the states in a prefix tree. Consequently, the generalisations acquired by merging states with the same neighbourhoods may be different. In the case of Asmat, the language obtained by merging same-neighbourhood states in the suffix tree is the same as the one returned by merging same-neighbourhood states in the prefix tree – it is the target language. But in the case of Lower Sorbian, the language obtained by merging same-neighbourhood states (in the suffix tree) is exactly the target language. In other words, this procedure avoids the overgeneralisation that the Forward Learner makes (again, see Heinz Reference Heinz, Wicentowski and Kondark2006 for details).

The learner which merges same-neighbourhood states in the suffix tree is called the Backward Neighbourhood Learner (BL). This learner identifies 96 of the 109 distinct patterns in the database, 82 of which the FL also identifies. As in the case of the FL, the error cases are ones of overgeneralisation. However, unlike the FL's errors, these occur predominantly in languages which are left-edge based.

Of course it is desirable to have a learner which does not know in advance whether to use a prefix or suffix tree. The FBL below is one such learner.

6.9 The Forward Backward Neighbourhood Learner

The FBL is very simple. Let M _nd be the function which maps an acceptor to the acceptor obtained by merging same-neighbourhood states. Let PT and ST denote functions which map a finite sample to the prefix tree and suffix tree respectively, which accepts exactly the given sample. The learner simply applies M _nd to the prefix and suffix tree representations of the samples and intersects the results.

1. (14) Algorithm 2: The Forward Backward Neighbourhood Learner

   Input: a positive sample S

   Output: an acceptor A

   Let A ₁=M_nd(PT(S))

   Let A ₂=M_nd(ST(S))

   Let A=A ₁ × A ₂ and output acceptor A

The product (×) of two acceptors A and B is also called the intersection of two machines, because this operation results in an acceptor which only accepts words accepted by both A and B (Hopcroft et al. Reference Hopcroft, Motwani and Ullman2001). In other words, L(A×B)=L(A)∩L(B). This learner succeeds on 100 of the 109 patterns (413 of 422 languages), a considerable improvement over the Forward and Backward Learners. Appendix A provides these results, along with those of the BL and FL. The following discussion below addresses why the learner works, and compares the learnable and unlearnable patterns to the attested typology.