Multi-Tiered Strictly Local Functions (2020)

Abstract: Tier-based Strictly Local functions, as they have so far been defined, are equipped with just a single tier. In light of this fact, they are currently incapable of modelling simultaneous phonological processes that would require different tiers. In this paper we consider whether and how we can allow a single function to operate over more than one tier. We conclude that multiple tiers can and should be permitted, but that the relationships between them must be restricted in some way to avoid overgeneration. The particular restriction that we propose comes in two parts. First, each input element is associated with a set of tiers that on their own can fully determine what the element is mapped to. Second, the set of tiers associated to a given input element must form a strict superset-subset hierarchy. In this way, we can track multiple, related sources of information when deciding how to process a particular input element. We demonstrate that doing so enables simple and intuitive analyses to otherwise challenging phonological phenomena.

## introduction many theoretical analyses of long-distance phonological patterns share the core intuition that a tier or projection of segments can allow for 'local' relationships to be established between non-adjacent elements by excluding material that is irrelevant from the implicated level of representation. for example, samala (also known as ineseño chumash) has a long-distance process of sibilant harmony in which an underlying /s/ surfaces as @xcite if another @xcite appears anywhere later in the word, as in /ha-s-xintila-was/ → [hasxintilawas] 'his former gentile name' @xcite . the harmony target can be arbitrarily far from the harmony trigger in the full string of segments, but the trigger and target are rendered adjacent on a level of representation containing all and only the sibilant consonants. within the subregular hierarchy of formal languages, the class of strictly local languages, which model local phonotactic restrictions @xcite @xcite have been extended to incorporate the notion of a tier, resulting in the class of tier-based strictly local (tsl) languages @xcite . likewise, the input strictly local (isl) and output strictly local (osl) functions-which characterize locallybounded phonological processes as subregular maps @xcite @xcite -have been generalized to the classes of input tier-based strictly local (itsl) and output tier-based strictly local (otsl) functions in order to account for non-local phonological processes @xcite @xcite . these tsl formal languages and functions successfully model a wide range of long-distance phonological patterns @xcite @xcite , and moreover have desirable properties for learnability @xcite @xcite . however, they suffer from a major drawback in that they are restricted to a single tier, and as a consequence are ill-equipped to deal with multiple, simultaneous long-distance dependencies. for example, the tamashek dialect of tuareg exhibits regressive long-distance sibilant harmony and regressive long-distance labial dissimilation @xcite . each of the two processes can be modelled in isolation as a tsl function, but there is no single tsl function that can apply both rules simultaneously. the solution we pursue in this paper is to give functions access to more than one tier. incorporating multiple tiers into a single function is relatively straightforward; the difficulty lies in understanding the computational properties of such functions and establishing appropriate restrictions on the number of tiers and the relationships between tiers. progress has been made with regards to properly restricting multi-tiered languages @xcite , and this paper considers the restrictions that need to be imposed onto the multiple tiers of a multi-tiered function. our proposal is to associate each input element with a set of tiers that must fall into a strict subset-superset hierarchy (i.e., each tier in the set is a strict subset of the next largest tier in the set, if it exists). the output corresponding to an input element then depends on its dedicated set of tiers, and no others. the rest of this paper is structured as follows. section 2 introduces the notation that will be used throughout the paper. section 3 presents the tsl functions as they are currently defined. section 4 discusses some limitations of tsl functions that this paper aims to address. section 5 formally defines the multi-tiered strictly local (mtsl) functions, and formalizes the restrictions that we propose must hold over the relationships among multiple tiers. section 6 demonstrates how appropriately restricted mtsl functions overcome the limitations highlighted in section 4. finally, section 7 concludes and provides directions for future research. ## preliminaries to start, let σ be an alphabet of symbols, which in the context of phonotactics represents a language's inventory of surface phones. a string w is a finite contiguous sequence of symbols from σ, and |w| denotes the length of w. we write λ for the unique string of length 0 (the empty string). we use σ * to denote the set of all strings of any length that can be made from elements in σ. note that σ * includes the empty string. given two strings u and v, we write u • v to denote their concatenation, though we will often simply write uv when context permits. a k-factor of a string w is any contiguous substring of w with length k, though in the special case that |w| ≤ k, w is its own and only k-factor. in what follows, fac k (w) denotes all the k-factors contained in a string w. a prefix of some string @xmath0. a suffix of some string @xmath1. note that any string is a suffix of itself, and that λ is a suffix of every string. when |w| ≥ n, suff n (w) denotes the unique suffix of w with a length of n; when |w| < n, it simply denotes w itself. given a string w and one of its prefixes u we write u -1 • w to denote w with u removed from its front. for example, ab -1 • @xmath2. finally, given a set of strings s, we write lcp(s) to denote the longest common prefix of s, which is the string u such that u is a prefix of every @xmath3, and there exists no other string v such that |v| > |u| and v is also a prefix of every @xmath4. a string-to-string function pairs every @xmath5, where σ and ∆ are the input alphabet and output alphabet respectively. given a set of input strings i ⊆ σ * , f (i) = @xmath6. an important concept is that of the tails of an input string w with respect to a function f . definition 1. tails @xcite given a function f and an input @xmath7, in words, tails f (w) pairs every possible string @xmath8. put another way, the tails of w are the effect that w has on the output of any subsequent string of input symbols. consider a function f computing post-nasal voicing. the tails of w 1 = /tan/ relative to f will include pairs such as t, d since f (tant) = [tand] and opu, opu since f (tanopu) = [tanopu]. when tails f (w 1 ) = tails f (w 2 ), we say that w 1 and w 2 are tailequivalent with respect to f . the string w 2 = /ken/ is tail-equivalent to w 1 with respect to f because they both end in a nasal consonant, and therefore both trigger post-nasal voicing. an example of a string that is not tail-equivalent to w 1 or w 2 would be w 3 = /sini/; its tail for /t/ is t, t since it does not end in a nasal consonant and so does not trigger post-nasal voicing. throughout the rest of this paper, we will need to be able to pick out the portion of the output that corresponds to actual input material. viewed from another perspective, we need to be able to ignore the portion of the output that would correspond to a word-end symbol. to make this distinction, @xcite defined the prefix function f p associated with a function f such that f p (w) is equal to the longest common prefix of all strings f (wx), where x is some member of σ * . ## background like their name suggests, the input strictly local (isl) and output strictly local (osl) functions take the strictly local (sl) languages as their base. theorem 1 states the property of the sl languages that allowed for the jump to isl and osl functions. this property is known as suffix substitution closure (ssc; @xcite . informally, if two grammatical strings share a middle portion of at least length k -1 (i.e., if w 1 = axb, w 2 = cxd, and |x| ≥ k -1), then we can substitute the suffixes that come after the overlap without causing ungrammaticality. a corollary of ssc is that any two grammatical strings from an sl k language that end in the same k-1 (or more) symbols can be legally continued by the exact same set of strings @xcite . theorem 1. suffix substitution closure @xcite a stringset l is strictly k-local if and only if whenever there is a string x of length k -1 and strings u 1 , u 2 , v 1 , v 2 , it is the case that: @xcite a stringset l is strictly k-local if and only if for all pairs w 1 , w 2 ∈ σ * : the definitions of the isl and osl functions take the property in corollary 1 and adapt it so that it applies to function tails. informally, a function f is isl if the tail-equivalence classes of f correspond to input suffixes, and a function f is osl if the tail-equivalence classes of f correspond to output suffixes (or more accurately, suffixes of f p ). ## limitations of tsl functions as discussed in @xcite , the tsl functions are quite versatile, being able to model long-distance harmony and long-distance dissimilation, both with and without blocking effects. this is, however, only the case when we model each phonological process of a language in isolation. consider the tamashek dialect of tuareg, which contains a process of long-distance regressive sibilant harmony and a process of long-distance regressive labial dissimilation @xcite . the sibilant harmony can be seen in words where the causative prefix /s-/ is followed non-locally by another sibilant, whereupon it takes that other sibilant's values for anteriority, voicing, and pharyngealization as shown by the data in (1) from @xcite . note that the language has considerable vowel allophony, and we write 'v' where @xcite does not provide the surface vowel quality. the labial dissimilation can be seen in words where a prefix /m/ (such as in the mediopassive) is followed non-locally by a labial consonant other than /w/, whereupon the prefix /m/ will dissimilate to @xcite . data for this process is shown in (2) from heath (2005, p. 472). that both processes can occur simultaneously is demonstrated by the word in (3) from heath (2005, p. 462), which contains the causative and mediopassive prefixes together. the combination of sibilant harmony and labial dissimilation cannot, however, be computed by a single tsl function. to see why, consider what happens when we try with an otsl 2 function whose tier consists of all sibilants and labial consonants. producing a sibilant will push the most recent labial consonant (if any) out of the k -1 window, and producing a labial consonant will push the most recent sibilant (if any) out of the k -1 window. at any given point, then, we can only know how to correctly map an input /s/ or only know how to correctly map an input /m/. increasing k does not eliminate the issue, since any number of sibilants can in principle occur between two labial consonants, and any number of labial consonants can in principle occur between two sibilants. a further difficulty for tsl functions posed by tamashek tuareg is that long-distance regressive labial dissimilation interacts with a local process of regressive nasal place assimilation. the complication arises from the fact that the local pro-cess overrides the long-distance process: /m/ fails to dissimilate specifically when it is immediately followed by an oral labial stop, in order to avoid a heterorganic cluster. this can be seen in a word like (4) from @xcite where the reciprocal prefix /vm-/ comes immediately before a /b/. we are faced with a paradox if we attempt to model this interaction as a single tsl function. in order to know when an input labial needs to dissimilate we need to ignore everything that is not a labial consonant, but in order to know when an input labial needs to obey place assimilation we cannot ignore anything. whether these interactions are problematic depends on whether we conceive of a language's phonological system as a series of input-output maps or as a single "master" input-output map. the latter position is explored by @xcite and @xcite in the context of formal language theory and automata theory. they remark that the isl functions are not closed under composition, but that certain opaque rule interactions (counterfeeding, counterbleeding, etc.) can nevertheless be modelled using a single isl function when the component rules are also isl functions. ## multi-tiered strictly local functions the main method that we will use to tackle the limitations presented in the previous section is by allowing a single function to operate over multiple tiers. we call these the multi-tiered strictly k-local (mtsl k ) functions, for lack of a better name. note that we use a large subscripted conjunction symbol to collapse a series of formulae that are identical aside from using different tiers. in words, there is a finite set of tiers such that if two input strings share a k -1 suffix on all tiers, then they will have the same tails. notice how this is a direct extension of the tsl k functions, since the singleton tier of a tsl k function will satisfy the above definition. of course, allowing any conceivable number of tiers and allowing any conceivable relationship between their contents is too powerful. one pathological behaviour that can arise from excessively free tier sets would be 'gang-up' effects. for example, given a collection of disjoint tiers that each contain a single element, we can describe processes where the output of some input element depends on the exact set of preceding elements regardless of their order. a similar behaviour can arise from overlapping but disjoint tiers. given τ 1 = {s, s, t} and τ 2 = {s, s, n} we could describe a process of sibilant harmony that is blocked only when both 't' and 'n' intervene, regardless of their order. to the best of our knowledge, such processes are unattested and should be excluded. in order to limit the "tier multiverse", we propose to reference the contribution of each σ ∈ σ separately, rather than referencing the entirety of tails f . informally, the contribution of a relative to w is the portion of f (wa) uniquely and directly attributable to a (e.g., it is what we would append to the output upon reading a in a transducer after having read w). a more formal definition is provided below. definition 11. contribution given a function f , some @xmath9, and some using this notion of a contribution relative to w, which singles out a single element of tails f (w), we place the following condition on mtsl k functions, which we call target specification. definition 12. target specification an imtsl k function f : σ * → ∆ * is target specified if for each σ ∈ σ there is a finite set t σ of tiers τ ⊆ σ that form a strict superset-subset hierarchy, and the following holds for all w 1 , w an omtsl k function f : σ * → ∆ * is target specified if for each σ ∈ σ there is a finite set t σ of tiers τ ⊆ ∆ that form a strict superset-subset hierarchy, and the following holds for all w 1 , w 2 ∈ σ * : in words, when an mtsl function is target specified, each σ ∈ σ (i.e., each potential target of one or more processes) can be associated with a group of tiers that together determine the contribution of σ. viewed from another perspective, each input element specifies the tiers that it wants to track, and the contribution of an input element can always be determined by tracking only its specified set of tiers; tracking other tiers provides information that is either redundant or irrelevant. importantly, each member of the tier group is a proper subset of the next largest member. requiring an input segment's multiple associated tiers to fall into a strict superset-subset hierarchy has two apparent positive consequences. first, this restriction will be beneficial for learning, since it drastically reduces the number of possible tier combinations that can influence a given input element. @xcite show that even with a small inventory of 10 elements, there are 1022 ways to create a supersetsubset pair, 511 ways to create a pair of fully disjoint sets, and 27990 ways to create a pair of partially overlapping sets. this last number is already 95% larger than the other two combined, and the difference only increases as the size of the alphabet grows. second, research into multitiered stringsets suggests that we never see a single restriction enforced on two partially overlapping tiers @xcite . ## multiple tiers in action this section now considers a range of individual patterns and pattern interactions that standard tsl functions are incapable of capturing. we show that each of the considered patterns and interactions are simply and intuitively captured by the targetspecified mtsl functions defined in the previous section. in order, we consider interactions between independent processes (6.1), interactions between conflicting processes (6.2), cases where a single target is subject to multiple harmonies (6.3), and cases where some segments act as last-resort harmony triggers in the absence of canonical triggers (6.4). ## conclusion this paper defined an extension of the tier-based strictly local functions, allowing them to track multiple tiers so long as the inter-tier relationships obey certain restrictions. rather than having the entirety of the functional tails depending on just one tier, we allow the contribution of each input element to separately depend on its own set of tiers, provided that the set falls into a strict supersetsubset hierarchy. our strategy of dividing the work amongst several independent sets of tiers greatly resembles the search procedure of nevins @xcite , see also @xcite . in this search procedure, specific input elements initiate a search for the nearest item relevant to them in some specified direction, and their output fate depends on the identity of the first relevant element found. our approach is in many ways the mirror of the search procedure: by tracking the tiers specified by σ, we preemptively remember the most recent element(s) that would be relevant to the output fate of σ, and we therefore always know what to do when σ is encountered. we demonstrated that a wide variety of otherwise challenging phonological processes receive simple and intuitive analyses from this perspective. a reviewer asks about the closure of the tsl functions under composition, pointing out that the mtsl languages are the closure of the tsl languages under intersection. while we have not yet formally proven so, it is likely that the leftreading mtsl functions are indeed the closure of the left-reading tsl functions under composition (mutatis mutandis for right-reading functions). at the very least, all of the language patterns analyzed in section 6 can be described as the composition of two same-direction tsl functions. similar to how @xcite and @xcite argue that the full class of mtsl languages is too powerful, though, we believe that our proposal of target specification is necessary since free composition of tsl functions can lead to processes with bizarre properties (see section 5). one noteworthy behaviour not covered by the proposed class is bidirectional application. research into bidirectional patterns has established that they can be modelled by weakly deterministic functions @xcite . these are those functions from σ * to ∆ * that can be modelled as a pair of subsequential functions that apply in sequence and meet the following criteria: (i) the two functions read in opposite directions, (ii) the first function is from σ * to σ * , and (iii) the first function is not permitted to increase the length of the string. since the function class considered in this paper is a proper subclass of the subsequential functions, it would be interesting to see whether we can lower the complexity bound of these bidirectional processes. namely, can we instead model them as a pair of mtsl functions running in opposite directions? finally, future work will consider the learnability of mtsl functions. @xcite showed that any otsl function is efficiently learnable from positive data if the tier is known in advance. this result can likely be carried over to mtsl functions once they receive a suitable automata characterization. when the tier is not known in advance, however, @xcite show that only total otsl 2 functions are learnable from positive data. the induction of multiple tiers, necessary for the learning of mtsl functions, will thus likely be a significant challenge. that being said, @xcite developed a method for learning the multi-tiered strictly 2-local languages, and their methods may perhaps be fruitfully applied to the function case.