A Logic Programming View of Relational Morphology

Harvey AbramsonCOLING 1992

TL;DR

This paper proposes a novel approach to computational morphology by reframing Koskenniemi's "two-level morphology" as a declarative relation computable via logic programming, specifically Prolog. This offers a more user-friendly and potentially more expressive alternative to traditional finite-state transducer implementations, enabling morphological analysis and generation within a unified logical framework.

What Problem Does This Paper Address?

The paper tackles the implementation and conceptualization of computational morphology, particularly Koskenniemi's influential "two-level model." While this model posits a mathematical relation between lexical and surface forms of words, its practical implementation has largely focused on finite-state transducers (FSTs). This FST-centric view, while efficient, can be cumbersome for users and may obscure the declarative nature of the underlying morphological rules. The authors argue that the "relation" aspect of Koskenniemi's work has been overlooked in favor of implementation details. They aim to bridge this gap by showing how these relational rules can be naturally expressed and computed using logic programming, offering a more abstract and potentially more powerful paradigm.

Methods

The core contribution is the reinterpretation of relational morphology rules within a logic programming framework, specifically using Prolog. The authors introduce a tableau notation for these rules and then provide a "logical reading" that translates these rules into Prolog clauses.

  • Declarative Notation: The paper uses a notation similar to Koskenniemi's, emphasizing the bidirectional relationship between lexical and surface forms.
  • Logic Programming Translation: Relational morphology rules are translated into Prolog clauses, primarily defining a morphology/2 predicate that relates lexical and surface streams. To handle contexts, a morphology/4 predicate is introduced.
  • Automatic Clause Generation: A small Prolog program is used to automatically generate these logic program clauses from the relational morphology rules.
  • Bidirectional Computation: The logic programming approach naturally supports both analysis (surface to lexical) and generation (lexical to surface) by querying the same set of Prolog clauses.
  • Efficiency: The authors suggest that compiled Prolog code for these clauses can be highly efficient, potentially outperforming interpretive methods and benefiting from Prolog compiler optimizations.

Datasets

Not discussed in the paper. The paper focuses on the formalization and implementation of morphological rules rather than empirical evaluation on specific datasets. The appendix provides examples of English plural formation rules.

Key Insights and Ideas

  • "Relational Morphology" over "Two-Level Morphology": The authors advocate for the term "relational morphology" to highlight the core concept of a mathematical relation between levels, moving beyond the implementation-specific "two-level" terminology.
  • Logic Programming as a Natural Fit: Logic programming, with its declarative nature and unification mechanism, is presented as an ideal paradigm for expressing and computing these morphological relations.
  • Unified Framework for Analysis and Generation: The logic programming approach elegantly handles both morphological analysis and generation using the same set of rules, a significant advantage over some FST-based systems.
  • User-Friendliness and Debugging: Logic programming environments, with their built-in tracing and debugging tools, are argued to be more user-friendly than the often complex and low-level FST programming paradigm.
  • Extensibility: Logic programming offers greater expressive power, making it easier to extend the formalism to handle more complex morphological phenomena, such as non-concatenative morphology.

Key Results

The paper primarily presents a conceptual and methodological contribution rather than quantitative results from extensive experiments.

  • Demonstration of Logic Programming Translation: The paper successfully shows how relational morphology rules can be translated into executable Prolog code.
  • Appendix with English Plural Rules: An appendix provides a concrete example of generating Prolog clauses for elementary English plural formation, illustrating the method.
  • Claim of Efficiency: The authors claim that compiled Prolog code can achieve significant speedups, especially for rules that compile down to simple unifications and recursive calls.
  • Improved User Experience: The logic programming approach is presented as a more user-friendly and maintainable alternative to FSTs.

Limitations and Future Work

  • Limited Empirical Evaluation: The authors acknowledge that the project is in its early stages and lacks an extensive set of examples. The paper does not present large-scale empirical evaluations of the system's performance or coverage.
  • Handling Non-Concatenative Morphology: While logic programming is suggested as a promising avenue for handling non-concatenative morphology, the paper only briefly touches upon this and does not provide detailed solutions.
  • Context Specification: The paper mentions that for complex contexts, a small logic grammar might be used to parse regular expressions, suggesting a potential area for further development.
  • Future Work: The authors plan to develop a full set of rules for English morphology and a specification of Japanese verb forms. They also suggest exploring metarules for dealing with non-concatenative aspects and investigating the use of more complex logic grammars for lexical context verification.

Summary updated

BibTeX
@inproceedings{abramson1992logic,
  author = {Harvey Abramson},
  title = {{A Logic Programming View of Relational Morphology}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1992},
}
Figure