Trees probe deeper than strings: an argument from allomorphy

Hossep Dolatian, Shiori Ikawa, Thomas GrafNAACL 2022

TL;DR

This paper argues that representing morphology with tree structures, rather than simple strings, reveals crucial complexity differences in allomorphy (variation in morpheme form). By analyzing different types of allomorphy, the authors show that tree structures can distinguish patterns that appear equally complex when viewed as strings, highlighting the importance of representation choice in linguistic theory and computation.

What Problem Does This Paper Address?

The field of morphology grapples with how to represent the internal structure of words. One fundamental question is whether morphemes are best modeled as linear strings or as hierarchical trees. While string-based models are common, this paper investigates whether tree structures offer a more nuanced understanding of morphological complexity, particularly in the phenomenon of allomorphy. Allomorphy occurs when a single morpheme has different phonetic forms depending on its context within a word. The authors focus on how the "trigger" morpheme's position (relative to the "target" morpheme whose form varies) and its adjacency to the target affect complexity. They hypothesize that tree structures, by explicitly encoding hierarchical relationships, might reveal complexity distinctions that are obscured in purely string-based analyses.

Methods

The paper employs formal language theory and finite-state transducers to model morphological processes. They compare string-based transductions (specifically, sequential transductions) with tree-based transductions (bottom-up and top-down sequential tree transducers). The core of their method involves analyzing four types of allomorphy: local/non-local and inwardly/outwardly sensitive. For each type, they formalize the phenomenon using both string and tree transductions and then compare the computational complexity classes required to capture them. A key aspect is the use of subregular complexity classes, which are subclasses of regular languages, to provide fine-grained distinctions. They introduce novel classes of sequential tree transductions and adapt existing string-based concepts to the tree domain.

Datasets

Not discussed in the paper. The paper uses attested examples from natural languages (Latin, Kiowa, Hungarian, Slovenian) to illustrate the phenomena, but does not present formal datasets for training or evaluation.

Key Insights and Ideas

  • Trees reveal hidden complexity: The central argument is that tree structures, by capturing hierarchical relationships, can distinguish between allomorphic patterns that appear equally complex when analyzed as linear strings.
  • Inward vs. Outward Sensitivity Matters on Trees: While string-based models show complexity differences primarily based on locality (local vs. non-local), tree-based models reveal an additional split between inwardly-sensitive and outwardly-sensitive allomorphy, particularly in the non-local case.
  • Unboundedness and Trees are Intertwined: The authors suggest that the need for tree structures and the assumption of unboundedness (allowing for potentially long-distance dependencies) are linked. When these assumptions are made, complexity differences emerge that are otherwise masked.
  • Subregular Classes as Diagnostic Tools: The paper leverages subregular complexity classes (like ISL and sequential transductions) as a precise way to measure and compare the computational demands of different morphological phenomena under different representational assumptions.

Key Results

The paper demonstrates that:

  • Local allomorphy (both inwardly and outwardly sensitive) is computationally equivalent whether modeled over strings or trees, falling within the ISL (Input Strictly k-Local) class.
  • Non-local inwardly-sensitive allomorphy is left-to-right sequential over strings and bottom-up sequential over trees.
  • Non-local outwardly-sensitive allomorphy is right-to-left sequential over strings. However, over trees, it requires more complex sensing tree transducers (which have a limited look-ahead) unless specific structural assumptions (like labeled interior nodes) are made, making it computationally more demanding than its inwardly-sensitive counterpart. This difference is the core finding.

Limitations and Future Work

  • Unboundedness Assumption: The findings regarding complexity differences for non-local allomorphy rely on the assumption of unboundedness. The paper acknowledges that inflectional morphology often exhibits limits on dependency length, and it's unclear if this is an intrinsic property or an accidental one.
  • Sensing Tree Transducers: The need for sensing tree transducers for non-local outwardly-sensitive allomorphy highlights a limitation of standard top-down sequential tree transducers and suggests a direction for future research in developing more powerful tree-based models for morphology.
  • Tier-Based Strict Locality: The authors suggest exploring tier-based strict locality as a potential framework to bridge the gap between ISL and sequential transductions, and to investigate its application to tree transductions.
  • Empirical Differences: The paper calls for empirical research to find actual linguistic differences between inwardly and outwardly sensitive allomorphy that can be explained by the observed computational complexity split.

Summary updated

BibTeX
@inproceedings{dolatian2022trees,
  author = {Hossep Dolatian and Shiori Ikawa and Thomas Graf},
  title = {{Trees probe deeper than strings: an argument from allomorphy}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2022},
}

Loading related content...

Figure