Trees probe deeper than strings: an argument from allomorphy (2022)

Abstract: Linguists disagree on whether morphological representations should be strings or trees. We argue that tree-based views of morphology can provide new insights into morphological complexity even in cases where the posited tree structure closely matches the surface string. Our argument is based on a subregular case study of morphologically conditioned allomorphy, where the phonological form of some morpheme (the target) is conditioned by the presence of some other morpheme (the trigger) somewhere within the morphosyntactic context. The trigger and target can either be linearly adjacent or non-adjacent, and either the trigger precedes the target (inwardly sensitive) or the target precedes the trigger (outwardly sensitive). When formalized as string transductions, the only complexity difference is between local and non-local allomorphy. Over trees, on the other hand, we also see a complexity difference between inwardly sensitive and outwardly sensitive allomorphy. Just as unboundedness assumptions can sometimes tease apart patterns that are equally complex in the finitely bounded case, tree-based representations can reveal differences that disappear over strings.

## introduction morphology can be taken to operate over either strings or trees. consider the simple case of english undoable, which is ambiguous between not doable with un-scoping over doable, and can be undone with -able scoping over undo. if one's primary concern is morphotactics, i.e. how morphemes can be arranged to obtain a well-formed word, then it is sufficient to represent undoable as a string un+do+able, consisting of three morphemes in a particular order. but this representation does not encode the scopal relations between the affixes un-and -able. linguists instead use trees to encode the scopal relations between the affixes un-and -able, giving us [un[do able]] and [[un do]able] for each respective interpretation of undoable. but strings and trees are vastly different data structures that greatly affect computational complexity. for instance, every dependency that is context-free over strings is only regular over trees. this paper explores the typology of allomorphy to probe how the choice between strings and trees can affect morphological complexity. our key insight is that even in cases where trees seem to add little over strings, trees can reveal complexity differences between empirical phenomena that are opaque at the string level. tree-based models are still rare in computational morphology, where morphological phenomena are usually modeled with finite-state machinery @xcite @xcite . from this perspective, morphological dependencies form regular string languages, and morphological processes can be computed by 1-way finite-state transducers. 1 in fact, many aspects of morphology are subregular over strings and fall within remarkably simple subclasses of regular string languages and finite-state transductions @xcite @xcite . there is little formal work on evaluating the expressivity of morphological dependencies and processes over tree-based representations. in particular, the fine-grained notions of subregular complexity have not been applied to tree-based views of morphology even though many subregular classes can easily be generalized from strings to trees. previous analyses of morphology that implicitly posit tree structure @xcite , do not explore the implications of tree structure for complexity, either. this paper seeks to demonstrate that this focus on string representations to the exclusion of tree structure means that subtle complexity differences between phenomena may be missed. it is not just cases like undoable where trees are useful, but even phenomena where the tree structure provides seemingly no additional information over the string representation. to this end, we contrast string-based and treebased views of morphologically conditioned allomorphy in terms of their subregular complexity. morphologically conditioned allomorphy covers phenomena where some morpheme (the target) has multiple possible realizations, the choice of which is conditioned by the presence of another morpheme (the trigger) within the word. crosslinguistically, morphologically-conditioned allomorphy can be parameterized in terms of directionality and the degree of locality between the target and trigger morpheme @xcite @xcite @xcite . if the trigger x is structurally lower than the target y, then allomorphy is inwardly-sensitive. if the trigger x is structurally higher than the target y, then allomorphy is outwardly-sensitive. if the target and trigger are structurally adjacent, then allomorphy is locally computed. if the target and trigger are non-adjacent, and if there can be one or more intervening morphemes, then the process is long-distance or non-local. typologically, local allomorphy is the most common in both directions. non-adjacent allomorphy is significantly less common, but attested @xcite . we find that these four types do not pattern the same way depending on whether one models them over strings or trees (see the paper is organized as follows. section 2 defines relevant families of string and tree transducers, including the (to the best of our knowledge) novel classes of bottom-up and top-down sequential tree transductions. in §3 and §4, we illustrate the typological parameters of allomorphy with attested examples from natural languages. in each section we formalize the respective type of allomorphy over strings as well as trees and contrast their complexity. we then synthesize the main insights in §5. we conclude in §6. ## mathematical preliminaries we cover several classes of subregular string and tree transductions in this paper. due to space constraints, we cannot give full definitions of each class, but the discussion in the subsequent sections is sufficiently straightforward on a formal level that the reduced rigor should not impact clarity. ## inwardly-sensitive allomorphy we now turn to local ( §3.1) and non-local ( §3.2) inwardly-sensitive allomorphy, followed by outwardly-sensitive allomorphy in §4. local inwardly-sensitive allomorphy can be modeled with isl fsts and by isl tree-transducers, suggesting that the choice between strings and trees is innocuous here. non-local inwardly-sensitive allomorphy only falls within those classes if one assumes a finite upper bound. otherwise, if no finite bound is assumed, then isl is insufficient, but the allomorphy phenomena can still be captured by left-to-right sequential string transducers or bottom-up sequential tree transducers. ## outwardly-sensitive allomorphy mirroring inwardly-sensitive allomorphy, outwardly-sensitive allomorphy is either local ( §4.1) or non-local ( §4.2). as we will see, local patterns are once again isl over strings as well as trees. if we model non-local patterns as involving potentially unbounded distances between the target and trigger, then these patterns are sequential over strings, but not necessarily over trees. ## discussion this paper surveyed the attested categories of local and non-local allomorphy, with the key findings summarized in the relevant complexity difference may seem minor compared to, say, the difference between regular and context-free dependencies, which greatly matters for practical purposes such as parsing. however, this is true for most subregular complexity differences. since all subregular dependencies and transductions can be handled with finite-state machinery, subregular distinctions do not impact efficiency. that does not mean, though, that the distinctions are irrelevant. they affect learnability, and they make different typological predictions about what kind of patterns we should expect to find across languages. one way to construe our finding, then, is that it urges us to look for empirical differences between inward non-local and outward non-local allomorphy that can be traced back to the gap in computational complexity. of course this argument hinges on the assumption that these phenomena are indeed unbounded and operate over trees. unboundedness is far from a given because inflectional morphology in natural language morphology usually exhibits limits on the linear distance between the targets and triggers of allomorphy. what is unclear is whether this is an intrinsic limitation of allomorphy itself or an accidental confluence of multiple independent factors. our findings provide a modus tollens argument to address this: if we do find differences between inwardly-sensitive and outwardly-sensitive allomorphy that can be explained in terms of the subregular complexity split, then that argues in favor of underlying unboundedness and morphological tree structures because that is the only case where we find a difference in subregular complexity. if there are no discernible differences, then either unboundedness or tree structure should be jettisoned for inflectional morphology. if there is evidence for both unboundedness and tree structure, that would be an interesting parallel to syntax. in fact, the split between inwardlysensitive and outwardly-sensitive allomorphy already has a connection to syntax. the sensing tree transducers of @xcite were motivated by the desire to address shortcomings of deterministic top-down transducers for syntax, so it is interesting that they are also needed for tree-based morphology with the unboundedness assumption. while the argument we present can be made with the coarse split between isl and sequential transductions, it would be interesting to explore a possible middle-ground between the two. tierbased strict locality has been explored in various areas -including phonology, morphology, and syntax -as an extension of the strict locality underpinning isl @xcite @xcite @xcite . the non-local case of allomorphy discussed in this paper may be describable along those lines. so far, no counterpart has been defined for tree transductions, but once this happens, the issues explored in this paper should be revisited from the perspective of tier-based strict locality. ## conclusion we have investigated four types of allmorphy from the perspective of strings and trees: local and nonlocal inwardly-sensitive allomorphy, and local and non-local outwardly-sensitive allomorphy. even though our tree structures closely track the surface strings, our findings are not the same over the two types of representations. while the split between local and non-local allomorphy always leads to a complexity difference if one assumes unboundedness, inwardly-and outwardly-sensitive allomorphy are equally complex over strings but not over trees. if there are empirical differences between these allomorphy types that can be derived from the split in complexity, that would provide evidence for both unboundedness and tree structure in inflectional morphology. our study thus highlights the importance of representations even in cases where the difference of representations seems innocuous at a first glance. an approach firmly rooted in trees and unboundendess may reveal subtle computational differences that would be missed otherwise.