Optimizing over subsequences generates context-sensitive languages

Optimizing over subsequences generates context-sensitive languages Andrew Lamont University of Massachusetts Amherst alamont@linguist.umass.edu Abstract Phonological generalizations are finite-state. While Optimality Theory is a popular frame- work for modeling phonology, it is known to generate non-finite-state mappings and languages. This paper demonstrates that Opti- mality 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. 1 Introduction Phonological generalizations are finite-state (Johnson, 1972; Kaplan and Kay, 1994; see Heinz, 2018, for a recent overview); that is, input- output mappings can be modeled using finite-state transducers and phonotactic well-formedness can be modeled using finite-state acceptors. Optimality Theory (OT; Prince and Smolensky, 1993/2004) is a framework that is commonly used to model phonology. While some restricted variants of OT are finite-state (Frank and Satta, 1998; Eisner, 2000, 2002; Riggle, 2004; see Hulden, 2017, for a recent overview), standard OT, as it is employed by practicing phonologists, is known to generate non-finite-state mappings and languages (Eisner, 1997; Frank and Satta, 1998). OT is a special instance of Harmonic Gram- mar (Legendre et al., 1990), which can model arbitrary computations (Smolensky, 1992). While the exact generative capacity of OT has not yet been characterized, it has recently been shown to produce non-context-free mappings (Lamont, 2019a,b). This paper contributes to the literature on OT by demonstrating its capacity to gener- ate 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 1Trivially, all strings of length 1 are subsequences. In this paper, subsequences refer to subsequences of length ≥ 2. substrings, whose constituent elements are con- tiguous. 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 (Heinz, 2007, 2010, 2014; Rogers et al., 2010; Graf, 2017). 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 when- ever possible. Consequently, in addition modeling non-local restrictions, constraints onto subsequences are often used to minimize the dis- tance between two objects (McCarthy and Prince, 1993; Hyde, 2012, 2016). 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 …

Content truncated to 500 words