A Complete and Recursive Feature Theory

Rolf Backofen, Gert SmolkaACL 1993 · DOI

Abstract

This foundational 1992 paper by Rolf Backofen and Gert Smolka establishes a complete first-order theory ($FT$) for feature descriptions, which serve as the logical counterparts to records or structs in programming. The authors demonstrate that this theory is decidable through a simplification algorithm and prove the logical equivalence of three distinct mathematical models: feature graphs, finite/infinite trees, and rational trees. This work provides a unified framework for constraint solving in logic programming and computational linguistics.

Introduction: The Logic of Feature Structures

In the early 1990s, researchers in computational linguistics and logic programming utilized "feature structures" to describe complex objects. Similar to JSON objects or C structs, these structures consist of attributes (features) pointing to values, which may themselves be typed (sorts). However, a theoretical gap existed: linguists favored cyclic "feature graphs," while logic programmers preferred "feature trees."

A feature tree representing a circle with a nested center point.

The primary challenge was the lack of a "complete" theory—one where every statement is provably true or false. Without completeness and decidability, constraint solvers cannot guarantee termination or find definitive answers.

Theoretical Framework: The $FT$ Theory

The authors define the theory $FT$ using three core axiom schemes:

  1. Functionality: Ensures features are functional; if $x f y$ and $x f z$, then $y = z$.
  2. Sort Disjointness: Prevents an object from belonging to multiple incompatible types simultaneously.
  3. Existence: Asserts that any consistent description corresponds to a real object in the universe.

To establish completeness and decidability, the authors employ Quantifier Elimination. They propose a terminating simplification algorithm that reduces complex logical formulas—including those with universal ($\forall$) and existential ($\exists$) quantifiers—into a "solved form."

Key Insights: Unifying Graphs and Trees

A significant contribution of this paper is the proof that feature trees and feature graphs are elementarily equivalent. Despite the structural differences—graphs allow cycles while trees are hierarchical—the authors show that first-order logic cannot distinguish between them under the $FT$ axioms.

A recursive feature structure representing natural numbers, illustrating the equivalence of cyclic graphs and trees.

This unification allows programming "records" to be treated as formulas in standard first-order logic, enabling the use of rigorous logical tools for data integrity and constraint reasoning.

Results and Impact

The paper successfully establishes $FT$ as a complete and decidable theory. Key outcomes include:

  • Unified Modeling: Proving that feature trees, rational feature trees, and feature graphs satisfy the same logical formulas.
  • Algorithmic Foundation: Providing a blueprint for efficient constraint solvers in languages like Oz and natural language processing systems.
  • Technical Innovation: Introducing the "joker" concept to manage path constraints during quantifier elimination.

Limitations

The theory assumes an infinite signature (infinitely many feature and sort names), which may require adaptation for systems with finite vocabularies. Additionally, while decidable, the worst-case computational complexity of quantifier elimination remains high.

Summary updated

BibTeX
@inproceedings{backofen1993complete,
  author = {Rolf Backofen and Gert Smolka},
  title = {{A Complete and Recursive Feature Theory}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1993},
  doi = {10.3115/981574.981600},
}

Loading related content...

Figure