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."
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:
- Functionality: Ensures features are functional; if $x f y$ and $x f z$, then $y = z$.
- Sort Disjointness: Prevents an object from belonging to multiple incompatible types simultaneously.
- 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.
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