Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Theorem Proving and CG Programming

Propagating truth and detecting contradiction in conceptual graph databases

John EschContact Information and Robert LevinsonContact Information

(1)  Loral Defense Systems - Eagan, P.O. Box 64525 U1T23, 55164 St. Paul, MN
(2)  Department of Computer Science, University of California, 225 Applied Sciences Building, 95064 Santa Cruz, CA
Abstract
In our ICCS95 paper, An Implementation Model for Contexts and Negation in Conceptual Graphs, we made some important advances relative to storing conceptual graphs in a generalization hierarchy. These included a simplified definition of both Formation and Inference Rules, a mechanism for storing nested, negative contexts, an extension to Method III for updating the database and truth values, a further extension to propagate some inferences, and a mechanism for representing and sometimes detecting contradictions. In this paper we show how to use properties of lattices and a context sensitive superresolution inference rule to propagate truth values in a database of nested, possibly negated, conceptual graphs and, as this is done, detect any consequent contradictions.
We show how a combination of adding data to the nodes and links of the CG hierarchy, maintaining the hierarchy as a lattice, inserting graphs insideout, and precomputing some values during earlier phases, leads to provably complete and more efficient algorithms than we described last year. An example is carried through the explanation of these new features to illustrate each. And, after the updated algorithm is presented, an efficient lattice based superresolution theorem proof procedure is presented.
An inductive proof is given that our insertion algorithm is also a proof procedure that retains consistency and completeness or detects contradiction. In first order databases, consistency and completeness are with respect to provability rather than truth.

Keywords  Conceptual Graphs - Generalization Hierarchy - Logic - Proof Procedure - Refutation - Resolution - Contradiction


Contact Information John Esch
Email: jesch@eag.unisysgsg.com

Contact Information Robert Levinson
Email: levinson@cse.ucsc.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.111 • Server: mpweb03
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)