Abstract
The DATR language is a widely used formalism for representing complex natural language lexicons, yet it has historically lacked a complete, mathematically rigorous foundation. This paper addresses this gap by redefining DATR as a formal system of partial functions. By introducing a "longest prefix" default mechanism, the proposed framework provides a declarative semantics that accounts for linguistic exceptions, global context, and dynamic rules, ensuring implementation independence and theoretical consistency.
Introduction
In Natural Language Processing (NLP), a lexicon is far more than a simple word list; it is a structured web of rules and exceptions. For instance, while most English verbs follow a regular past tense formation (e.g., walk to walked), irregular verbs (e.g., run to ran) necessitate a system capable of handling overrides. DATR was specifically designed as a "non-monotonic" language to manage such hierarchies.
However, early formalizations of DATR were incomplete, failing to account for global context—where a rule's meaning depends on the initial query point—or "evaluable paths" (dynamic rules). Without a formal mathematical semantics, researchers could not guarantee consistent behavior across different implementations or formally analyze the language's computational complexity.
Formalizing DATR Semantics
The author, Bill Keller, shifts the perspective of DATR from a traditional "semantic network" (nodes and arrows) to a functional programming paradigm. The core of this approach involves treating each node as a partial function mapping a "path" (a sequence of linguistic features) to a "value."
The Interpretation Triple
Keller defines a formal model based on the triple $(U, \kappa, F)$:
- $U$: The set of possible values.
- $\kappa$: A mapping of global contexts to functions.
- $F$: An assignment of meanings to specific atoms and nodes.
The Default Interpretation ($\Delta$)
A central innovation of this work is the formalization of the "longest prefix" rule. In DATR, if a specific path is not explicitly defined, the system identifies the longest matching prefix that is defined and applies its rule. This mathematically captures the intuitive behavior of "inheriting unless specified otherwise."
Lexical Representation Example
To illustrate these formal concepts, the paper utilizes a fragment of an English verb lexicon. This hierarchical structure demonstrates how abstract categories and specific lexemes interact through inheritance and overrides.
As shown in Figure 1, nodes like Verb serve as base categories, while EnVerb and Aux represent sub-categories. Specific lexemes like Mow or Can inherit properties from their parent nodes but can override them to handle irregularities.
Key Insights
- Global Context as State: Global inheritance is modeled not as a static link, but as a mechanism tracking the query's origin. This allows descriptors to change meaning based on the "starting point" of the lookup.
- Limitations of the Network Metaphor: While boxes and lines are useful for visualization, they fail to represent "evaluable paths"—where the path itself is the result of another lookup. Keller’s functional approach handles these dynamic cases where static graphs fail.
- Descriptors as Families: Descriptors are modeled as families of values indexed by path extensions, allowing default logic to propagate mathematically through the system.
Conclusion and Future Work
This research provides the first complete declarative semantics for the entire DATR language, including strings and global inheritance. By formalizing the "longest prefix" rule, the paper establishes a "gold standard" for DATR implementations, ensuring they produce correct results regardless of the underlying algorithm.
Future research enabled by this framework includes investigating the computational complexity of DATR queries and developing formal correctness proofs for optimized implementation strategies, such as graph-based virtual memory systems.
Summary updated