Optimizing over subsequences generates context-sensitive languages (2021)

Abstract: Phonological generalizations are finite-state. While Optimality Theory is a popular framework for modeling phonology, it is known to generate non-finite-state mappings and languages. This paper demonstrates that Optimality Theory is capable of generating non-context-free languages, contributing to the characterization of its generative capacity. This is achieved with minimal modification to the theory as it is standardly employed.

## introduction phonological generalizations are finite-state @xcite ; see @xcite , for a recent overview); that is, inputoutput mappings can be modeled using finite-state transducers and phonotactic well-formedness can be modeled using finite-state acceptors. optimality theory (ot; @xcite ) is a framework that is commonly used to model phonology. while some restricted variants of ot are finite-state @xcite @xcite ; see @xcite , for a recent overview), standard ot, as it is employed by practicing phonologists, is known to generate non-finite-state mappings and languages @xcite . ot is a special instance of harmonic grammar @xcite , which can model arbitrary computations @xcite . while the exact generative capacity of ot has not yet been characterized, it has recently been shown to produce non-context-free mappings @xcite . this paper contributes to the literature on ot by demonstrating its capacity to generate non-context-free languages using constraints defined over subsequences. subsequences are finite literals composed of ordered symbols that are not necessarily adjacent. 1 they contrast with substrings, whose constituent elements are contiguous. figure 1 illustrates the subsequences of length 2 in the string example. of these twenty-one subsequences, six are also substrings of length 2: e. . . x, x. . . a, a. . . m, m. . . p, p. . . l, l. . . e. in the literature on phonotactics as formal languages, subsequences have been used to model non-local phenomena @xcite @xcite @xcite . for example, if a language disallows words from surfacing with more than one lateral consonant, it can be modeled as banning the subsequence l. . . l. languages defined by banning a finite set of subsequences belong to the strictly piecewise languages, which are properly contained within the class of regular languages. strictly piecewise languages impose inviolable constraints on subsequences: a string belongs to a language if and only if it does not contain any banned subsequences. in ot, all constraints are violable, and violations are minimized whenever possible. consequently, in addition to modeling non-local restrictions, constraints on subsequences are often used to minimize the distance between two objects @xcite @xcite . for example, figure 2 illustrates a string of syllables, represented as σ, that belong to a prosodic word, whose edges are marked with square brackets. two syllables are parsed into a foot, indicated by parentheses. the number of ) . . . σ . . . ] subsequences indicates how far the foot is from the right edge of the prosodic word, calculated over intervening syllables. when only one foot is parsed, aligning it to the right edge of the prosodic word eliminates ) . . . σ . . . ] subsequences: [σσσσσ(σσ)]. however, they are unavoidable when multiple feet are parsed. in these cases, the pressure to minimize ) . . . σ . . . ] subsequences determines the prosodification. for example, optimization and violability contribute much more expressivity than these results suggest. @xcite demonstrated that ot can generate context-free languages with subsequence constraints, and this paper pushes his result into non-context-free languages. the main result of this paper has wide-reaching consequences for phonologists, as many standard constraint families are defined over subsequences. examples include alignment constraints @xcite @xcite , conjoined constraints @xcite @xcite , co-occurrence constraints @xcite , share constraints @xcite , and the family of surface corre- parse total [(σ)(σσ)(σσ)(σσ)] 12 [(σσ)(σ)(σσ)(σσ)] 11 [(σσ)(σσ)(σ)(σσ)] 10 [(σσ)(σσ)(σσ)(σ)] 9 ## violable subsequence constraints can divide strings into halves eisner @xcite demonstrated that with violable constraints on subsequences, mappings in optimality theory can target the centers of strings. in his example, the midpoint pathology, a feature in the input shifts so as to surface in the center of the output. taking stress as that feature, the midpoint pathology is defined in (1) as an input-output mapping, where σ represents a syllable, and σ represents a stressed syllable. the output language is homomorphic to the archetypal non-finite-state language a n b n , with the allowance of an additional a or b. the tableau in as this example demonstrates, shifting stress onto the medial syllable minimizes the violations of align(σ, σ, σ); see section 3 for a proof that this holds for any length input. @xcite @xcite is an artifact of the symmetrical nature of align(σ, σ, σ). in particular, if the constraint penalized only σ . . . σ . . . σ or σ . . . σ . . . σ subsequences and not both, then stress would be drawn to one edge rather than the center. the tableau in while asymmetrical constraints avoid the midpoint pathology specifically, they motivate other mappings that target the centers of strings. for example, the constraint allfeet-right @xcite @xcite penalizes ) . . . σ subsequences that occur within a prosodic word. by restricting its application to a given prosodic word, allfeet-right is similar to but distinct from penalizing ) . . . σ . . . ] subsequences. as discussed in section 1, this constraint pulls monosyllabic feet to the right edge of prosodic words, and as the tableau in in practice, prosodic words typically reflect morphosyntactic structure. however, because the constraints that enforce such correspondences are violable (such as the family of match constraints; @xcite , mappings like those illustrated in the balanced prosodic word mapping is defined in (4). like the midpoint pathology, its application depends on identifying the center syllable, and its output language is homomorphic to a n b n with an extra a or b. thus, even though asymmetric alignment cannot target the center of a prosodic word, it can target the center of a string parsed into two prosodic words. the mappings in this section depend on the same underlying mechanism: divide a string of syllables into two parts, and minimize the subsequences of at least length 2 that occupy each part. this reduces the difference in size between the two parts to at most one syllable. with the midpoint pathology, the two parts are defined by syllables that precede the stressed syllable and syllables that follow the stressed syllable. with balanced prosodic words, the two prosodic words define the parts. this mechanism is independent of the subsequences themselves, provided that they are at least of length 2. thus, restricting which subsequences a constraint can penalize can only block specific mappings. no restrictions on the set of subsequences prevents them from dividing strings in half. this is proved formally at the end of section 3. the mappings in this section only divided strings into two equal parts, generating context-free languages. the next section presents mappings that divide strings into three or more equal parts, generating non-context-free languages. ## violable subsequence constraints can divide strings into arbitrarily many equally sized parts as the previous section demonstrated, subsequence constraints can be used to divide strings into two equal parts, generating context-free languages. parsing strings into more than two equal parts generates non-context-free languages. with balanced prosodic words, this follows from parsing a string of syllables into more than two prosodic words. this can be motivated by hierarchical prosodic structure @xcite , rather than stipulated arbitrarily. figure 3 illustrates a standard five-level prosodic hierarchy, where prosodic words are dominated by phonological phrases, which are dominated by an intonational phrase. by requiring these top two levels to dominate exactly two daughter nodes, the string of syllables is parsed as expected, allfeet-right has two effects on strings parsed into four prosodic words. first, in odd-parity prosodic words, the monosyllabic foot appears at the right edge. second, no two prosodic words differ in size by more than one syllable. the tableau in as noted in the previous section, allfeet-right is distinct from a constraint that penalizes ) . . . σ subsequences. in particular, because it is restricted to subsequences within prosodic words, it undercounts when multiple prosodic words are parsed, as figure 4 illustrates. the next case study demonstrates that this property is irrelevant to the generative capacity of ot with subsequence constraints. to that end, consider the constraint *x. . . x defined in (6). *x. . . x is a non-local variant of *geminate that penalizes subsequences of length 2 whose constituent segments are identical. it has not been proposed as a serious phonological ) . . . σ subsequences indicated with solid lines, and not the three indicated with dashed lines. /llllllll/ *x. . . x ident(lateral) a. llllllll 28 + 0 = 28 b. lllllllr 21 + 0 = 21 1 c. llllllrr 15 + 1 = 16 2 d. lllllrrr 10 + 3 = 13 3 → e. llllrrrr 6 + 6 = 12 4 the tableau in this mapping is defined in (7). its output language is context-free, and homomorphic to permutations of a n b n with the usual allowance of an additional a or b. to generate a context-sensitive stringset with this constraint, one just has to consider a third segment type. the tableau in the mappings in this section demonstrated constraints over subsequences dividing strings into a fixed number of groups of equal size. in all cases, if the groups were not exactly equal, they could differ by at most one element. this generalizes to strings of all lengths and all numbers of groups: minimizing the difference between group sizes minimizes the number of violating subsequences. before presenting a proof of this result, it is necessary to establish that subsequences of length 2 grow quadratically in a string's length, in particular, a string of length n has n 2 -n 2 subsequences of length 2. as a base case, a string of length 2 has 1 such subsequence: 2 2 -2 2 = 1. inductively, assume that a string of length n has n 2 -n 2 subsequences of length 2. adding one segment adds n subsequences of length 2, and it can be verified that n 2 -n 2 + @xmath0 proof. for a string s composed of k disjoint sets, let s 1 , s 2 , . . . , s k denote the cardinality of each set, and define the constraint function m : @xmath1 let u be a string composed of k disjoint sets such that one set has two more members than another: by way of contradiction, assume that the composition u minimizes the function m . consider an alternate composition v, identical to u except that one element has been moved from the larger set to the smaller set: by assumption, we have m (u) < m(v), from which we derive a contradiction: this contradicts the fact that u i is at least as great as u j + 2. therefore, no composition of a string whose component sets differ in cardinality by two or more minimizes m . this proves that violable constraints in optimality theory that penalize subsequences of length 2 can divide any length input into a fixed number of equally sized parts, generating context-sensitive stringsets. ## conclusion optimality theory is known to generate nonfinite state mappings and languages @xcite , even with constraints defined over strings @xcite @xcite @xcite . this paper contributes to this literature by demonstrating that constraints over subsequences generate context-sensitive languages under optimization. this result has wide-ranging impacts for the field of phonology, as a number of commonly employed constraint types are defined over subsequences.