A Three-Valued Interpretation of Negation in Feature Structure Descriptions

A THREE-VALUED INTERPRETATION OF NEGATION IN FEATURE STRUCTURE DESCRIPTIONS Anuj Dawar Dept. of Comp. and Info. Science University of Pennsylvania Philadelphia, PA 19104 K. Vijay-Shanker Dept. of Comp. and Info. Science University of Delaware Newark, DE 19718 April 20, 1989 ABSTRACT Feature structures are informational elements that have been used in several linguistic theories and in computa- tional systems for natural-language processing. A logi- caJ calculus has been developed and used as a description language for feature structures. In the present work, a framework in three-valued logic is suggested for defining the semantics of a feature structure description language, allowing for a more complete set of logical operators. In particular, the semantics of the negation and implication operators are examined. Various proposed interpretations of negation and implication are compared within the sug- gested framework. One particular interpretation of the description language with a negation operator is described and its computational aspects studied. 1 Introduction and Background A number of linguistic theories and computational ap- proaches to parsing natural language have employed the notion of associating informational dements, called feature structures, consisting of features and their values, with phrases. Rounds and Kasper [KR86, RK86] developed a logical calculus that serves as a description language for these structures. Several researchers have expressed a need for extending this logic to include the operators of negation and impli- cation. Various interpretations have been suggested that define a semantics for these operators (see Section 1.2), but none has gained universal acceptance. In [Per87], Pereira set forth certain properties that any such interpretation should satisfy. In this paper we present an extended logical calculus, with a semantics in three-valued logic (based on Kleene's three-valued logic [Kh52]), that includes an interpretation of negation motivated by the approach given by Kart- tunen [Kar84]. We show that our logic meets the condi- tions stated by Pereira. We also show that the three-valued framework is powerful enough to express most of the pro- posed definitions of negation and implication. It therefore makes it possible to compare these different approaches. 1.1 Rounds-Kasper Logic In [Kas87] and [RK86], Rounds and Kasper introduced a logical formalism to describe feature structures with dis- junctive specification. The language is a form of modal propositional logic (with modal operator ":'). In order to define the semantics of this language, fea- ture structures are formally defined in terms of acyelic finite automata. These are finite-state automata whose transition graphs are acyclic. The formal definition may be found in [RK86]. A fundamental property of the semantics is that the set of automata satisfying a given formula is upward-closed under the operation of subsumption. This is important, because we consider a formula to be only a partial descrip- tion of a feature structure. The property is stated in the following theorem IRK86]: Theorem 1.1 A C 8 if and only i/for every formula, ~, if A ~ ~ then B ~ cb. 1.2 The Problem of Adding Negation Several researchers in the area have suggested that the logic described …

Content truncated to 500 words