TL;DR
This paper investigates why the Two-Level Morphology (TLM) model, while theoretically capable of describing computationally complex phenomena, remains efficient in practice for languages like Finnish. The authors argue that the limited number of phonological processes (especially harmony) in natural languages, rather than the TLM formalism itself, is the key to this practical efficiency.
What Problem Does This Paper Address?
The Two-Level Morphology (TLM) model is a powerful framework for describing phonological and morphological phenomena in languages, particularly for word inflection, derivation, and compounding. It's implemented using finite-state machines and has proven highly effective for processing languages like Finnish, even on resource-constrained systems. However, a recent theoretical analysis by Barton (1986) suggested that TLM could be NP-hard, implying that processing could become computationally intractable. This raises a crucial question: if TLM is theoretically capable of complex computations, why is it so efficient in practice for natural languages? The paper aims to reconcile this apparent contradiction by exploring the relationship between the theoretical complexity of TLM and the actual complexity of natural language grammars.
Methods
The paper delves into the theoretical underpinnings of the TLM model, explaining its three representations (morphological, lexical, surface) and the systems (lexicon, phonological rules) that relate them. It then discusses Barton's theoretical argument, which involves constructing an artificial grammar to demonstrate how TLM can be reduced to a satisfaction problem, thus showing its potential for computational difficulty. The authors counter this by proposing that the size of the grammar, specifically the number of phonological processes (like vowel harmony), is the critical factor for practical efficiency. They analyze the typical number of such processes in natural languages and present empirical evidence from Finnish to support their claim that processing time is linear with word length, not exponentially dependent on grammar size.
Datasets
The paper uses a word list compiled from two samples of the Finnish newspaper Helsingin Sanomat, comprising approximately 400,000 running words. This list was augmented with all Finnish words of 17 or more letters from the corpus and about 700 additional running text words. This dataset was used to measure recognition time as a function of word length.
Key Insights and Ideas
- The "Grammar Constant" Assumption: The practical efficiency of TLM in natural languages is largely due to the fact that natural language grammars, particularly their phonological rule sets, are relatively small and fixed. This allows for a "grammar constant" assumption, meaning processing time is primarily driven by input length, not grammar complexity.
- Harmony Processes as the Bottleneck: Barton's NP-hardness result stems from the potential for a large number of harmony processes. However, natural languages rarely exhibit more than two such processes, significantly limiting the theoretical complexity that is actually realized.
- Finnish as a Case Study: The paper uses Finnish to demonstrate that despite its rich morphology, the TLM model's application is efficient. Empirical data shows a linear relationship between word length and recognition time, contradicting the exponential complexity predicted by Barton's theoretical reductions for large grammars.
- Distinction Between Theoretical and Practical Complexity: The core insight is that theoretical complexity (how a system can be used) doesn't always reflect practical complexity (how it is used in real-world applications). Natural languages, by their very nature, seem to avoid the extreme grammatical structures that would lead to computational intractability in TLM.
Key Results
- Empirical experiments with Finnish word lists show that recognition time is linear with word length, with a slope of approximately 2.43 steps/letter.
- This linear relationship holds even when considering all words, and is further strengthened when ambiguous words are excluded.
- The paper categorizes natural languages based on the number of vowel harmony processes they employ: zero (88%), one (Uralic, Tungusic, Sahaptian), or two (most Altaic languages). This limited number of processes is crucial for practical efficiency.
Limitations and Future Work
- Artificial Grammars vs. Natural Languages: The paper acknowledges that Barton's NP-hardness result is demonstrated using artificial grammars with an arbitrary number of harmony processes. The authors argue this is not representative of natural languages.
- Ambiguity: The paper notes that ambiguity in words can increase processing time, as seen with the outlier "lakiasiaintoimistoa." Further investigation into how ambiguity affects TLM performance could be valuable.
- Grammar Size and Performance: While the paper focuses on the number of harmony processes, the overall size and structure of the lexicon and rules could also influence performance. The authors suggest that a careful analysis of time and space performance is needed to fully understand why TLM is efficient for Finnish.
- Future Work: The authors implicitly suggest that further empirical studies on various languages would be beneficial to confirm the universality of their findings regarding the limited number of phonological processes in natural languages.
Summary updated