A Finite State Approach to German Verb Morphology

Gunther Gorz, Dietrich PaulusCOLING 1988

TL;DR

This paper introduces a novel, language-independent Finite State Transducer (FST) model for analyzing and generating German verb morphology. It tackles the complexity of German verb inflection by treating rewriting rules as operating on entire surface words, rather than individual letters, enabling a more efficient and generalizable approach.

What Problem Does This Paper Address?

Morphological analysis and generation, especially for highly inflected languages like German, has traditionally been a complex challenge. Existing systems were often language-specific and struggled with the vast number of possible word forms. While Finite State Transducers (FSTs) offered a promising direction for formalizing linguistic rules computationally, prior approaches often relied on sequential, letter-by-letter processing or complex rule ordering. This paper aims to overcome these limitations by proposing a more efficient and generalizable FST-based model that can handle the intricacies of German verb morphology, including stem vowel changes, and can be applied to other languages as well.

Methods

The core of the proposed approach is a "parallel rewriting variant of FSTs" that operates on complete surface words. Unlike previous methods that processed words letter by letter, this system applies rewriting rules to entire word forms simultaneously. This is achieved by defining rules with a Pattern -> Replacement scheme, where both pattern and replacement can include a wildcard character that matches the same letter in both. This parallel processing, combined with feature unification for linguistic information, allows for a single FST to handle both analysis and generation. The system also incorporates a letter-tree lexicon for efficient storage and retrieval of lexical information, annotated with feature lists.

Datasets

The paper mentions that the system has been tested with lexicons and rules covering:

  • All of German verb morphology.
  • Interesting subsets of French and Spanish verbs.

No specific datasets are detailed, but the focus is on applying the model to existing linguistic data for these languages.

Key Insights and Ideas

  • Parallel Word-Level Rewriting: The most significant innovation is the shift from letter-by-letter processing to applying rewriting rules on entire surface words. This dramatically simplifies the computational model and improves efficiency.
  • Language Independence: The FST-based approach, particularly with its parallel rewriting mechanism, is designed to be language-independent, allowing for application to various inflected languages.
  • Feature Unification: The system leverages feature unification, a standard technique in computational linguistics, to manage and combine linguistic information associated with word forms.
  • Lexicon as a Letter Tree: Using a letter tree for the lexicon, annotated with feature lists, provides an efficient way to store and access lexical entries, avoiding redundancy.
  • "Shell" for Language-Specific Phenomena: The authors propose a "shell" around the generic FST model to handle language-specific complexities like German stem vowel changes, without altering the core FST mechanism.

Key Results

The paper reports on a successful implementation of the system on a PC. While specific quantitative results like accuracy percentages are not provided, the authors state:

  • The system has been successfully tested with lexicons and rules covering all of German verb morphology and significant portions of French and Spanish verb morphology.
  • A practical experience section mentions that a previous implementation using only rewriting rules showed a runtime improvement of over 75 percent compared to the extended algorithm.
  • Analysis performance is reported as less than 1 second per verb form with non-optimized LISP code.

Limitations and Future Work

  • Manual Automaton Coding: Currently, there is no compiler to automatically generate an automaton from a given set of rules; the automaton has to be coded manually.
  • Stem Vowel Location: While the "shell" approach addresses the problem of locating stem vowels, the paper acknowledges this as a hard problem in German verb inflection that requires specific handling.
  • Lexicon Size: The paper discusses strategies to keep the lexicon small by avoiding the explicit listing of all possible stem vowel changes.
  • Future Work: The authors suggest that the general FST-based model can be extended to handle other linguistic phenomena by wrapping specialized modules around the core algorithm. The focus is on creating a generalized framework for lexical representation and efficient word stem recognition.

Summary updated

BibTeX
@inproceedings{gorz1988finite,
  author = {Gunther Gorz and Dietrich Paulus},
  title = {{A Finite State Approach to German Verb Morphology}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1988},
}
Figure