1 Introduction
It has been known for a long time that the phonological systems of natural languages are finite-state in nature and thus generate regular languages (Johnson Reference Johnson1972, Kaplan & Kay Reference Kaplan and Kay1994). However, this characterisation is insufficient, in the sense that phonological dependencies instantiate much simpler patterns – regular languages only provide an upper bound on phonological expressivity. This realisation has led to increased efforts in recent years to pinpoint the computational nature of phonology more precisely (Heinz Reference Heinz2009, Reference Heinz2010, Graf Reference Graf2010a, Reference Grafb, Rogers et al. Reference Rogers, Heinz, Fero, Hurst, Lambert, Wibel, Morrill and Nederhof2013, Chandlee Reference Chandlee2014, Jardine Reference Jardine2016).
The abovementioned research relies on results presented by McNaughton & Papert (Reference McNaughton and Papert1971), which are reviewed in Rogers & Pullum (Reference Rogers and Pullum2011). Phonological considerations have led to the study of two more subregular classes of languages and their relation to those previously established (Rogers et al. Reference Rogers, Heinz, Bailey, Edlefsen, Visscher, Wellcome, Wibel, Ebert, Jäger and Michaelis2010, Heinz et al. Reference Heinz, Rawal and Tanner2011). Taken together, this research shows how to divide the regular languages into complexity classes, allowing the degree of pattern complexity to be understood with greater precision. A tentative consensus has emerged that the strictly local (SL), strictly piecewise (SP) and tier-based strictly local (TSL) classes – and the grammars that generate languages in these classes – provide reasonable approximations of natural language phonotactics. These classes are among the least complex in the hierarchy, and have cognitive interpretations (Rogers et al. Reference Rogers, Heinz, Fero, Hurst, Lambert, Wibel, Morrill and Nederhof2013).
However, the claims about the empirical suitability of these classes implicitly assumes that phonological generalisations apply uniformly across a given domain, such as the word. Decades of research have established that phonological generalisations are sometimes best understood as involving multiple domains, with generalisations applying only within or across smaller or larger ones. The literature is so extensive that only some highlights are provided here (Rubach Reference Rubach2008, Selkirk Reference Selkirk, Goldsmith, Riggle and Yu2011, Scheer Reference Scheer, Bloch-Trojnar and Bloch-Rozmej2012 and Shwayder Reference Shwayder2015 provide recent surveys). Kiparsky (Reference Kiparsky, van der Hulst and Smith1982) posits a major distinction between word-level and sentence-level processes, couched in terms of Lexical Phonology and its various domains of rule application. Booij & Rubach (Reference Booij and Rubach1984) argue that we also need a split between morphological and prosodic domains within words, while Kaye (Reference Kaye, Durand and Katamba1995) proposes a more general system, where words may be structurally decomposed into subdomains, reminiscent of how syntactic trees are made up of phrases of various sizes. In the other direction, there is also plenty of evidence for phonological domains above the word level but below the sentence level, such as intonational phrases (Selkirk Reference Selkirk1984, Nespor & Vogel Reference Nespor and Vogel1986). And feet and syllables have of course proven indispensable in the analysis of stress patterns (Hayes Reference Hayes1995). Given the central role of domains in phonology, it is imperative that their study be part of the subregular analyses of phonology.
In this paper I show how domains increase the expressivity of the SP class. The first result establishes that if domains can be postulated freely, the resulting class – domain-based strictly piecewise (DBSP) – subsumes every subregular class except the regular class itself. The second result shows that the increase in expressive power is much less pronounced if the domains must be natural from a linguistic perspective. Specifically, smaller domains must delimit specific intervals within a larger domain. I call the resulting class interval-based strictly piecewise (IBSP) grammars.
There are many advantages to understanding phonotactic patterns in terms of the IBSP class. The SL, SP and TSL classes are contained within IBSP, so any phonotactic pattern expressible with any of those grammars is expressible with an IBSP grammar. IBSP is more than the sum of these three classes, however. This increased expressivity is useful to capture unbounded tone plateauing, which is outside the SL, SP and TSL classes. Also, the increased expressivity of IBSP is much less than that of DBSP. IBSP excludes certain kinds of unnatural phonotactic patterns that DBSP does not. Finally, IBSP is naturally parameterised in a way that permits learnability results. I conclude that phonological domains are thus a welcome and highly useful addition that unifies phonologically natural subregular regions – but they must be interval-based and not arbitrary, lest the formalism lose most of its restrictive force.
A clarification is in order regarding the scope of the paper. While some work in the subregular literature has focused on the mappings from underlying forms to surface forms (see Chandlee Reference Chandlee2014, Chandlee et al. Reference Chandlee, Eyraud and Heinz2014, Reference Chandlee, Eyraud, Heinz, Kuhlmann, Kanazawa and Kobele2015 and references therein), this paper and the subregular classes mentioned above are about phonotactic generalisations, i.e. surface forms. The formalisms discussed here only need to be able to distinguish well-formed surface forms from ill-formed ones; underlying representations are never considered. Nonetheless, I will sometimes describe certain phenomena such as tone plateauing as a process. This is merely a convenient expository device, and only the surface forms produced by these processes are relevant to this paper.
The paper is laid out as follows. §2 familiarises the reader with the phonologically important subregular classes SL (§2.1), SP (§2.2) and TSL (§2.3). Their formal commonalities and empirical differences are briefly outlined in §2.4. Building on these observations, I show in §3.1 that enriching SP grammars with locality domains allows for an elegant account of several problematic phenomena, but at the cost of severe overgeneration. Limiting domain restrictions to precisely defined intervals, on the other hand, keeps generative capacity in check (§3.2). §3.3 explains why this limitation is also essential for learnability.
2 Subregular phonotactics
The later sections of this paper require the reader to be familiar with the subregular classes SL, SP and TSL and how they are defined as fragments of first-order logic. I present only the essentials here. Readers familiar with first-order logic and these subregular classes can skip ahead to §2.4, where I contrast the three from an empirical perspective. Readers interested in a thorough exposition of first-order logic are invited to consult the textbooks Ebbinghaus et al. (Reference Ebbinghaus, Flum and Thomas1996) and Enderton (Reference Enderton2001). For the subregular classes and how they relate to phonotactics, readers are referred to the overviews presented in Heinz (Reference Heinz2010, Reference Heinz, Hyman and Plankto appear). Technical treatments of these classes are given in Rogers et al. (Reference Rogers, Heinz, Fero, Hurst, Lambert, Wibel, Morrill and Nederhof2013) and Heinz et al. (Reference Heinz, Rawal and Tanner2011).
2.1 Strictly local grammars
In the subregular approach to phonology, the simplest model of phonotactics is provided by strictly local grammars. A strictly k-local (SL-k) grammar is a finite set of k-grams, each one of which is a description of an illicit sequence of segments. Consider for instance the strictly 2-local grammar {⋊V, CC, VV, C⋉}, where ⋊ and ⋉ denote the left and right edge of the string respectively. This grammar forbids all words that start with a vowel (⋊V), contain two adjacent consonants (CC) or vowels (VV), or end in a consonant (C⋉). In other words, this grammar describes a language with a CV syllable template. It essentially forbids certain substrings of length 2.
Note that C and V are used for the sake of brevity. If the language in question has only the vowels [a] and [u], plus the consonants [p] and [k], the set of sequences that violate the CV template could be compiled out into the twelve bigrams in (1).Footnote 1
-
(1)
We can increase the length of the k-grams to capture phonotactic generalisations with an extended locality domain. Consider a markedness constraint against intervocalic voiceless fricatives. An SL-3 grammar {VFV} (where F stands for any voiceless fricative) accomplishes this. An SL-2 grammar is insufficient. Banning bigrams VF and FV does not succeed, because either is fine as long as F is not both immediately followed and immediately preceded by vowels. A grammar that operates with bigrams is therefore either too permissive or too restrictive; only trigrams are large enough to correctly capture this markedness constraint.
SL grammars can be recast in terms of formulas of first-order logic, and this logical perspective is important for the remainder of the paper, in particular §3. I refrain from giving a full exposition of first-order logic here – a purely intuitive treatment suffices for our purposes. One may think of the grammar for intervocalic voicing above as a single constraint that can be expressed directly in first-order logic, as in (2).
-
(2)
In this formula, the use of x 1 S x 2 to indicate that x 2 immediately follows x 1 is motivated by the mathematical convention to call x 2 the successor of x 1. As discussed next, replacing S by another relation yields a very different formalism (Rogers et al. Reference Rogers, Heinz, Fero, Hurst, Lambert, Wibel, Morrill and Nederhof2013).
2.2 Strictly piecewise grammars
SL grammars – despite their simplicity – provide a reasonable model of local dependencies in phonology, including those created by iterated processes such as progressive vowel harmony. But they provably cannot regulate dependencies that involve two segments that may be arbitrarily far apart. An example of this is sibilant harmony in Samala, as discussed in Heinz (Reference Heinz, Hyman and Plankto appear), based on data from Applegate (Reference Applegate1972). In Samala, no word may contain both [s] and [∫], irrespective of how far the two are apart. Suppose one wanted to account for this with an SL-k grammar. This grammar would need to ban all k-grams that contain both [s] and [∫]. For example, with k=3 the grammar would include C s∫, C∫s, ∫C s, s C∫, s∫C, ∫s C, and all the counterparts where C is replaced by V. But such an SL-k grammar enforces sibilant harmony only as long as the two sibilants are separated by at most k®2 segments. If they are further apart, they do not belong to the same k-gram, and hence are outside the grammar's purview. Long-distance processes are therefore beyond the capabilities of SL.
A simple way of accounting for such unbounded dependencies is to maintain the k-gram approach, but change how k-grams are interpreted. In an SL grammar, the bigram s∫ indicates that [s] must not be immediately followed by [∫]. But if we switch from immediately follow (the relation S) to follow at any distance (the precedence relation ≺), k-grams enforce unbounded dependencies instead of local ones. Under this interpretation, the strings [s∫] and [∫s] are subsequences of length 2, and, as such, any string containing either subsequence is considered ill-formed. Grammars where k-grams enforce such unbounded dependencies are called strictly k -piecewise (SP-k; Rogers et al. Reference Rogers, Heinz, Bailey, Edlefsen, Visscher, Wellcome, Wibel, Ebert, Jäger and Michaelis2010).
The first-order logic perspective reveals the close parallel between SL and SP. Both use the same template for formulas, but different relations. Consider the SL and SP formulas for the set {s∫, ∫s}. They are identical, modulo the relation that holds between x 1 and x 2.Footnote 2
-
(3)
While the SL interpretation of {s∫, ∫s} only enforces harmony under adjacency, the SP interpretation applies harmony across the entire string.
2.3 Tier-based strictly local grammars
Most attested dependencies that hold within a phonological word are either SL or SP, but some require even more power. While there are several ways in which those outliers could be handled, a natural approach from a linguistic perspective involves tier-based strictly local (TSL) grammars (Heinz et al. Reference Heinz, Rawal and Tanner2011). TSL grammars are SL grammars with a tier-projection mechanism (cf. Goldsmith Reference Goldsmith1976, Vergnaud Reference Vergnaud, Butts and Hintikka1977) that creates new locality relations. The SL grammar then restricts the arrangement of tier-adjacent segments rather than string-adjacent segments. Whether a segment ends up on the tier (a TSL grammar has only one tier) depends solely on whether its label is listed in the ‘tier alphabet’ – the structural surroundings of a segment are irrelevant.
A particularly clear demonstration of how TSL differs from SL and SP is primary word stress (Heinz Reference Heinz and van der Hulst2014). It is a general property of phonological words that they have exactly one syllable carrying primary stress. Now consider a language where primary stress can be an unbounded number of syllables away from any word edge, e.g. because it sometimes falls on the rightmost heavy syllable, which may be close to the middle of the word. Under such circumstances, neither SL nor SP can guarantee the presence of stress.
Consider two words of the form σσ…σσ́σ…σσ and σσ…σσσ…σ, where σ denotes unstressed and σ́ stressed syllables. The first word obeys the requirement for exactly one primary stress, whereas the latter only contains unstressed syllables, and thus violates it. The first word contains the bigrams ⋊σ, σσ, σσ́, σ́σ and σ⋉. The second word only contains ⋊σ, σσ and σ⋉. But note that all these bigrams are also part of the first string. Since an SL-2 grammar can only forbid illicit strings by forbidding certain bigrams, the string without primary stress can be marked as ungrammatical by banning at least one of its bigrams. But then the well-formed string with exactly one primary stress would be ruled out too. For the very same reason, the grammar cannot generate σσ…σσ́σ…σσ without also generating σσ…σσ́σ…σσ́σ…σσ. These counterexamples generalise to arbitrary SL-k grammars, showing the inadequacy of SL grammars for primary stress.
SP grammars improve on this, as they can rule out words with two primary stresses. The strictly 2-piecewise grammar {σ́σ́} prevents a stressed vowel from being followed by another stressed vowel, and thus no word can contain more than one primary stress. However, this captures only one half of the requirement that words have exactly one primary stress; it still remains to ensure that every word has at least one primary stress. SP grammars are incapable of doing this, because all the subsequences of σσ…σσσ…σσ are also subsequences of σσ…σσ́σ…σ. As in the case of SL, one cannot exclude the latter and still generate the former, and this holds for all SP-k grammars. Neither SL nor SP grammars, then, can enforce the presence of at least one primary stress.
A TSL grammar solves the challenge by positing a stress tier. This tier contains all segments, and only those, that carry primary stress (in other words, the tier alphabet consists of all possible instances of σ́). By convention, the word edges are also part of the tier. If a word contains no primary stress at all, the primary stress tier will be empty. If it contains at least two primary stresses, then the primary stress tier contains at least two segments. The only licit configuration on the tier is ⋊σ́⋉ – a word with exactly one primary stress. These tier dependencies are SL-2 because we only have to forbid ⋊⋉ (no primary stress) and σ́σ́ (more than one primary stress).
The example shows how TSL grammars are endowed with a mechanism for creating new locality domains so that non-local dependencies become local. These domains take the form of tiers, which ignore all segments that do not belong to a specified type T. The logical formulas for this example in (4) show this.
-
(4)
The formula in (4a) looks exactly like an SL formula, except that S is replaced by S T , which is defined in (b) to hold between two segments iff they are both projected onto the tier T and no segment between them is also present on this tier. Tiers thus replace S with S T , a restricted version of the precedence relation ≺.
Adding a restricted version of ≺ to SL in order to obtain TSL increases expressivity of the system in a desirable way. Another approach, however, is to introduce local domains to SP. This is the idea pursued in §3.
2.4 Relations between the three classes
SL, TSL and SP carve out different, but overlapping subregular regions.
SL and SP are incomparable. This means there exist patterns which belong to both classes, as well as patterns which only belong to one and not the other. TSL properly subsumes SL because any SL grammar can be modelled with a TSL grammar which puts every element on the tier.
Like SL, TSL is incomparable to SP. We saw in the previous section that the restriction to exactly one primary stress per word is TSL but not SP. In the other direction, circumambient processes (Jardine Reference Jardine2016) constitute SP patterns that are not TSL. Circumambient processes have an interval-like nature: between two segments x and y, all z’s must have a specific shape.
A concrete instance is unbounded tone plateauing, which requires that no low tone may occur between two high tones, no matter how far apart those two high tones are. From the perspective of SP, this amounts to blocking HLH. TSL, on the other hand, cannot accommodate this dependency. Since both high tones and low tones are involved, both must be projected on the tier. There is no set of k-grams that can be used to forbid ill-formed sequences like HLnH for all n>1. This is because sequences like HLn and LnH are well-formed for every n≥0, including cases where n≥k. But for such a large n, an SL-k grammar will also generate HLnH, because no local constraint is violated – the two high tones are so far apart that the grammar cannot ‘see’ the H…H configuration.
Although unbounded tone plateauing is SP, there is something unsatisfactory about the way SP accounts for it. Remember that the SP grammar simply rejects every string where L follows H and is itself followed by H, no matter how far apart the three are and what occurs between them. This constraint picks out the correct strings only if we assume a one-to-one relation between strings and phonological words. If strings consist of multiple words in some phrase, then SP grammars cannot enforce this constraint. To see why, consider the string ⋊$HLL$LLH$⋉, where $ is used for the word-edge marker to clearly distinguish it from the string-edge markers. This string does not violate tone plateauing, thanks to the intervening word boundary, yet the SP grammar counts the string as ill-formed because it contains the subsequence HLH – the word boundary is not taken into account. Thus unbounded tone plateauing is only SP if the dependencies are restricted to word domains.
The next section explores this point more carefully. I first show that arbitrary first-order domain restrictions on SP grammars are actually not restrictions at all. Then I show that once domains are restricted to intervals, so that they more closely resemble phonological proposals, a more appealing picture emerges. A key result is that SL and TSL reduce to special cases of SP grammars operating on interval domains. Then, instead of an SL class for local processes, an SP class for non-local processes and a TSL class for a little bit of both, there is one unified grammar that combines SP grammars with locality domains.
3 Adding locality domains
3.1 Domain-based strictly piecewise grammars
Let us now look at one way an SP grammar can be limited to a domain (§3.1.1). We will see why this takes the expressivity of the resulting formalism beyond what appears to be needed for phonology (§3.1.2).
3.1.1 Definition and examples
Intuitively, confining an SP-k dependency between segments x 1, x 2, …, x k to a specific locality domain D means that the dependency must be satisfied only if all x i are inside D (1≤i≤k). From the perspective of first-order logic, this is tantamount to making D the antecedent of an implication.Footnote 3
-
(5)
Here φ p denotes the first-order equivalent of the labelling information inherent in the strictly piecewise k-gram p (cf. §2.1). For instance, the bigram ab corresponds to the formula a(x 1)∧b(x 2). The ∧ operator acts as a shorthand for multiple conjunctions. Assuming that the grammar contains only the bigrams ⋊a, aa and a⋉, the expanded formula would be (6).
-
(6)
Due to the structure of the formula in the definition in (5), the conditions enforced by the SP grammar need to be met by positions x 1, …, x k only if the domain requirement D is satisfied. Note that D can be any first-order formula, so it need not even mention the variables x 1, …, x k . Furthermore, the formulas for SL, SP and TSL are instances of the template above, where D is a conjunction of statements of the form x i R x j , with R set to S, ≺ or ST (cf. (3), (4a)).
DBSP grammars solve the abovementioned problem of SP grammars with unbounded tone plateauing. The problem with the SP account in §2.4 is that it fails whenever the ban against HLH subsequences applies to domains that are larger than a single word. Consider the DBSP-3 grammar G:=⟨P, W⟩, where the SP grammar P only contains the trigram HLH. The domain restriction W guarantees that P only applies within words, as in (7). (I assume that word edges are explicitly marked by $.)
-
(7)
This formula encodes a simple statement: x 1, x 2 and x 3 must occur between word-edge markers l and r that are not separated by another word-edge marker z. In other words, x 1, x 2 and x 3 must belong to the smallest interval spanned by two $ markers. This is the first-order expression for a word domain. The DBSP grammar ∀x 1, x 2, x 3[W → ¬φH L H] then says that the three positions are subject to the requirement enforced by the trigram HLH only if condition W holds.
The full first-order sentence for G with W and φH L H expanded is given in (8), to illustrate how the different pieces of the grammar are combined into a single formula.
-
(8)
In this way DBSP grammars can require constraints to hold only within certain domains.Footnote 4
3.1.2 Overgeneration: DBSP=star-free
While the ability of DBSP to handle unbounded tone plateauing is welcome, it comes at the price of massive overgeneration: the class of DBSP languages is exactly the class of star-free languages. A language is star-free iff it can be defined in first-order logic (McNaughton & Papert Reference McNaughton and Papert1971). While star-freeness may be a necessary condition on phonotactic patterns, it is arguably not a sufficient one, because phonologically outrageous dependencies can be expressed with first-order logic, as shown in (9).
-
(9)
Consequently, the equivalence of DBSP and the star-free languages entails that locality domains allow for the generation of very unnatural patterns.
However, an even stronger result holds: every star-free language is DBSP-1. So no matter how much one constrains the SP component of a DBSP grammar, the domain restrictions can always make up for any loss of expressivity obtained by weakening the SP grammar, as in (10).
-
(10)
The proof of this equivalence exploits the permissive definition of domain restrictions. Recall from §3.1.1 that a DBSP grammar only requires domain restrictions to be first-order formulas. The domain restriction D is then inserted into the general template in (11).
-
(11)
But this procedure is so general that D can be used to impose arbitrary constraints as long as they are first-order definable. And the star-free languages are exactly those that can be defined by arbitrary first-order definable constraints.
Even though arbitrary domain restrictions grant SP grammars too much power, this does not force us to forgo them completely – instead, we should tighten our notion of what domain restrictions may look like.
3.2 Interval-based strictly piecewise grammars
While mathematically correct, the proof of Theorem 1 seems to violate the spirit of what phonological locality domains are about. Instead of picking out certain substructures within which a constraint applies, the domain restriction acts as the constraint, while the SP grammar is trivialised to a nonsensical ban against left word edges. Moreover, it is certainly not the case that any first-order formula is a possible phonological domain. Looking once more at our treatment of tone plateauing in §3.1.1, our primary interest is not to define tightly interwoven conditionals, as in the outrageous example in (9), but rather to delineate specific intervals within a string – and this intuition is also the foundation of phonological notions like feet, syllables and words. As I show next, a proper formalisation of intervals (§3.2.1) does indeed go a long way to fix the overgeneration problems of DBSP (§3.2.2).
3.2.1 Introducing k-intervals
SP constraints which apply within phonologically motivated intervals must specify three items (cf. Jensen Reference Jensen1974, Odden Reference Odden1994). First, the edges of the interval must be specified, e.g. that the left and right edges are labelled $ in the domain W presented earlier. Second, the interval must contain a given number of positions, which are subject to the constraints of the SP grammar. So an interval for an SP-k grammar contains k such positions, denoted by x 1, …, x k in the first-order formulas. Finally, there is an additional stipulation on what the remainder of the interval may look like. All these requirements can be represented by an extension of k-grams that I call k- vals (short for k-intervals).
The advantage of k-vals is that they provide a much more readable specification of complex first-order formulas such as W. Consider once more the DBSP grammar ⟨P, W⟩, which forbids HLH subsequences within individual words. We can depict W as a 3-val that requires the edges to be labelled $, contains three open slots that are subject to the SP grammar and ensures that no other material within this interval (the fillers) is labelled $, as in Fig. 1.
3-val for W.
These k-vals are more constrained than arbitrary first-order formulas, as we may only specify the number and shape of open slots, the labels of the edges, and what the other positions in the interval may look like. Nonetheless, k-vals are still remarkably flexible. In fact, they are so flexible that SP grammars with k-vals as domain restrictions subsume SL and TSL grammars.
Every SL-k grammar can be reinterpreted as an SP grammar with a k-val that forbids any fillers. Assuming that every node must be labelled l 1, l 2 or l 3, and so on, this is tantamount to the demand that no filler is labelled l 1, l 2 or l 3, and so on. Take as a concrete example the SL-2 grammar from (1), which generates words with a CV syllable template over the sound inventory [a], [u], [p], [k]. An SP grammar with exactly the same bigrams describes the same CV syllable template if it is coupled with the 2-val in Fig. 2.
2-val for emulating an SL-2 grammar.
This 2-val can only match intervals where the two empty open slots are adjacent to each other. As a result, the long-distance dependencies of the SP-2 grammar are limited to adjacent segments, making it behave exactly like an SL-2 grammar.
So far our k-vals have displayed a certain asymmetry, in that fillers are always restricted, edges are sometimes restricted and empty slots are never restricted. Eliminating these asymmetries allows us to also emulate standard SP grammars and, more interestingly, TSL grammars. The inclusion of SP is straightforward: if the k-val puts no restrictions on any segments, then there are no inhibitions on the operation of SP grammars, as shown in Fig. 3.
3-val for emulating an SP-3 grammar.
TSL arises from a k-val format that is only slightly more complicated than that for SL. In the case of SL, we wanted to prevent any segments from intervening between open slots. For TSL, we allow fillers as long as they are not part of the tier alphabet T. On the flip side, the open slots are restricted to members of the tier alphabet – or, the other way round, they must not be segments that are not members of the tier alphabet; see Fig. 4.
2-val for emulating a TSL-2 grammar.
This largely exhausts the range of options for k-vals. For the sake of generality I also allow the left and right edges to be associated with different properties, so that an interval may span from, say, a vowel to a specific consonant. But this minor extension does not change the general fact that k-vals are extremely impoverished in comparison to arbitrary first-order formulas. In fact, each component of a k-val amounts to a ban against specific labels. Such bans are SL-1 (or equivalently, SP-1), which is the weakest class in the whole subregular hierarchy. So k-vals define locality domains by a combination of the weakest conceivable grammars, yet when they are added on top of SP grammars they are surprisingly expressive, and subsume SP, SL and TSL, while also handling circumambient processes correctly.
3.2.2 Formal definition and generative capacity
With the intuition firmly established, the formal definition of interval-based strictly piecewise- k (IBSP-k) should be much easier to grasp, and it will also be straightforward to prove that there are DBSP languages that are not IBSP. This strongly suggests that IBSP currently offers the best solution to integrate domain restrictions with phonotactic patterns: it subsumes the phonologically natural classes SL, SP and TSL, and also captures circumambient dependencies, yet remains much more restrictive than DBSP.
I first define k-vals as a combination of four SL-1 grammars, two of which restrict the edges, one the open slots and one the fillers. Each k-val corresponds to a first-order formula, as in (12).
-
(12)
The overly powerful DBSP class is pruned down to the linguistically more plausible IBSP class by limiting the domain restrictions to k-val formulas, as in (13).
-
(13)
Thanks to our observations on Figs. 2–4, we already know that IBSP contains all languages that are SL, SP or TSL. But IBSP also goes slightly beyond those classes, because it can still express the domain restriction W, and thus accounts for circumambient processes in a straightforward manner, as in (14).
-
(14)
In fact, the existence of circumambient patterns such as tone plateauing is now completely expected, because it merely involves co-opting mechanisms of the grammar that are already employed to restrict SP dependencies to the word domain, capture SL and TSL patterns, and so on. And these mechanisms are remarkably weak: k-vals define locality domains with a combination of SL-1 grammars, which define arguably the weakest class of formal languages in the subregular hierarchy. Yet when these intervals restrict SP constraints, they furnish a surprising degree of expressivity.
While more expressive than these other subregular grammars, IBSP grammars are still incapable of generating many unattested patterns. This can be inferred from the fact that they are strictly weaker than DBSP grammars, as shown in (15).
-
(15)
The DBSP language used in the proof is a formal counterpart to the unattested process of first-last harmony (see Lai Reference Lai2015 for details). IBSP fails to capture first-last harmony, because it cannot integrate the local dependency of word-edge adjacency with the non-local harmony constraint. It is known that first-last harmony is locally testable and thus belongs to a more powerful extension of SL. So first-last harmony is still a fairly simple pattern, but the limitations of IBSP explain why it nonetheless does not seem to arise in phonology.
Its inability to integrate local with non-local information also ensures that IBSP captures the old adage that ‘languages do not count’. Consider a language L, which contains only strings with at most one instance of [an]. For an IBSP account, we might try to use the word domain W, and forbid anan. But this will also rule out strings where [a] and [n] are not adjacent. If we forbid fillers in order to ensure adjacency, then only adjacent instances of [an] (as in [banana]) are disallowed. So a word may contain multiple instances of [an], as long as they are far away from each other. The same problem arises if we take [a] or [n] to be one of the word edges: as soon as adjacency is enforced, we can no longer enforce the long-distance dependency of at most one [an] in the whole word domain. A similar argument can be used to show that the variant of L that contains at least two instances of [an] is not IBSP. This kind of arbitrary counting is impossible with IBSP. Where counting effects seem to obtain, as with primary stress assignment, they have to be so simple that they can be captured via purely structural means, e.g. tier projection.
As a hypothesis about the computational nature of phonotactics, then, IBSP predicts that there should be no attested patterns that integrate local and long-distance dependencies in the manner suggested by the previous examples. This does not seem to be entirely true; at least one counterexample is discussed in Heinz (Reference Heinz2007) and McMullin (Reference McMullin2016). McMullin explains that sibilant harmony in Samala, which was briefly discussed in §2.2 as an example of an SP pattern, can overrule a general ban against string-adjacent [sn], [sl] and [st]. That is to say, sequences like [sn] are forbidden unless there is another [s] somewhere to the right of [n]. De Santo & Graf (Reference De Santo and Graf2017) take this pattern as the motivation to enhance TSL grammars with a more powerful, structurally conditioned tier-projection mechanism. While these grammars correctly capture this interaction between a local and a non-local dependency, IBSP is once again incapable of doing so. The reason is exactly the same as before: in order to enforce adjacency for some segments in the locality domain, we have to enforce adjacency for all segments, which makes it impossible to handle the long-distance dependency correctly.
To sum up, IBSP is incomparable with many subregular language classes, and thus less expressive than DBSP. For the most part, the limited expressivity of IBSP is a good thing, but a minor extension will be needed in the future to handle cases like the example from Samala, where local and non-local information interact. This also includes suprasegmental phenomena such as tone spreading in Copperbelt Bemba (Jardine Reference Jardine2016) and certain stress patterns (Reference BaekBaek to appear).Footnote 5 Nonetheless, IBSP grammars offer an insightful and empirically viable unification of all phonologically interesting subregular classes posited so far (cf. (16)) – a unification that is grounded in locality domains, one of the most natural of linguistic concepts.
-
(16)
3.3 Learnability
The large gap in expressivity between DBSP and IBSP highlights the restricted nature of locality domains in phonology, but it is also an essential factor for learnability. It is a well-known fact that star-free languages are not learnable in the limit from positive text (a corollary of them properly subsuming the class of finite languages; Gold Reference Gold1967). Consequently, the expressively equivalent class DBSP cannot be learned in the limit from positive text either.
However, IBSP-k is learnable for any fixed choice of k. This learnability claim is trivial, once one realises that there can be only finitely many distinct languages in this class for any choice of k. There are only finitely many SP-k grammars, because with an alphabet of size n there are n k distinct k-grams and thus 2(n k) distinct grammars. The number of distinct k-vals is similarly limited, to (2n)4=24n, because a k-val consists of four unigram grammars. As a result, the number of IBSP-k languages is at most 2(n k)×24n. While this number is enormous, Gold (Reference Gold1967) proves that every finite language class is learnable, no matter how large it is; see (17).
-
(17)
This still leaves open whether IBSP-k is efficiently learnable from just a small amount of data. I suspect that this strong condition holds, mainly because IBSP treats locality domains as combinations of SL-1 dependencies, which are efficiently learnable in isolation. More generally, SL-k and SP-k are efficiently learnable as well, as is TSL (Jardine & Heinz Reference Jardine and Heinz2016, Jardine & McMullin Reference Jardine, McMullin, Drewes, Martín-Vide and Truthe2017). The methods there may be applicable to this case as well. Finally, I also expect that phonologically motivated naturalness conditions (clustering segments into classes, minimum prominence demands for interval edges, and so on) greatly prune down the number of possible k-vals, tremendously reducing the amount of required data.
Even if my conjecture turns out to be false, the fact that IBSP is learnable whereas DBSP is not confirms the long-held belief that UG-restrictions on locality domains aid learnability (Heinz Reference Heinz2007, Reference Heinz2009, Reference Heinz2010). A child that comes already equipped with the assumption that dependencies involve k elements and may only be relativised to locality domains of a specific shape can successfully learn any language in the hypothesis space.
4 Conclusion
The main insight of this paper is that locality domains simplify our current picture of subregular phonology rather than complicate it. IBSP grammars unify the SL, TSL and SP classes by amplifying SP grammars with interval-based domain restrictions. There are a number of welcome consequences to introducing these locality domains, listed in (18).
-
(18)
This paper constitutes a first step towards a more thorough exploration of how locality domains may be effectively incorporated into the study of subregular patterns in language. Formally, establishing an abstract characterisation of the IBSP class will help in identifying phonotactic patterns that do and do not belong to this class. Empirically, since the domains within which phonological processes apply have been studied by linguists for many years, attempts to further generalise and refine these findings can draw from numerous ideas in the literature. Careful exploration of the formal ramifications of such modifications should yield an even tighter characterisation of natural language phonotactics, and might also prove fruitful in other areas such as syntax and morphology.Footnote 6 It will also be interesting to see whether the expressivity gap between segmental and suprasegmental phonology noted by Jardine (Reference Jardine2016) can be derived from linguistic assumptions about their respective locality domains.
