A Logical Semantics for Nonmonotonic Sorts

A LOGICAL SEMANTICS FOR NONMONOTONIC SORTS Abstract Suppose we have a feature system, and we wish to add default values in a well-defined way. We might start with Kasper-Rounds logic, and use Reiter's example to form it into a default logic. Giving a node a default value would be equiv- alent to saying "if it is consistent for this node to have that value, then it does." Then we could use default theories to describe feature structures. The particular feature structure described would be the structure that supports the extension of the default theory. This is, in effect, what the theory of nonmonotonic sorts gives you. This paper describes how that the- ory derives from what is described above. Mark A. Young &~ Bill Rounds Artificial Intelligence Laboratory The University of Michigan 1101 Beal Ave. Ann Arbor, MI 48109 marky, rounds©engin, umich, edu The original presentation of nonmonotonic sorts provided only a description of their operation and an informal description of their meaning. In this paper, we present a logical basis for NSs and non- monotonically sorted feature structures (NSFSs). NSFSs are shown to be equivalent to default theo- ries of default logic (Reiter 1980). In particular, we show how nonmonotonic sort unification is equiv- alent to finding the smallest default theory that describes both NSFSs; and also how taking a solu- tion for a NSFS is the same as finding an extension for that theory. INTRODUCTION There have been many suggestions for incorporat- ing defaults into unification-based grammar for- malisms (Bouma 1990; Bouma 1992; Carpenter 1991; Kaplan 1987; Russell et al. 1992; Shieber 1986; Shieber 1987). Each of these proposes a non-commutative, non-associative default unifica- tion operation that combines one structure repre- senting strict information with another represent- ing default information. When presented with a set of structures, the result depends on the order in which the structures are combined. This runs very much against the unification tradition, in which any set has a unique most general satisfier (if a satisfier exists at all). A method that is free of these ordering effects was presented in (Young 1992). The method of nonmonotonic sorts (NSs) allows default labels to be assigned at any time, and used only in the ab- sence of conflicting information. NSs replace the more traditional labels on feature structures to give nonmonotonically sorted feature structures (NS- FSs). These structures can be combined by an asso- ciative and commutative unification operation. FSs are rederived from NSFSs by taking a solution--an operation defined in terms of information present in the NSFS. FEATURE SYSTEMS Unification-based grammar formalisms use formal objects called feature structures to encode linguis- tic information. We use a variant of the standard definition. Each structure has a sort (drawn from a finite set 8), and a (possibly empty) set of at- tributes (drawn from a finite set ~). Definition1 A feature structure is a tuple (Q, r, 6, O) where • Q is a finite set of nodes, • r E Q is the root node, …

Content truncated to 500 words