Improving the Forward Chaining Algorithm for Conceptual Graphs Rules

Jean-François Baget

SimpleConceptual Graphs (SGs) are used to represent entities and relations between these entities: they can be translated into positive, conjunctive, existential first-order logics, without function symbols. Sound and complete reasonings w.r.t. associated logic formulas are obtained through a kind of graph homomorphism called projection. Conceptual Graphs Rules (or CG rules) are a standard extension to SGs, keeping sound and complete reasonings w.r.t. associated logic formulas (they have the same form as tuple generating dependencies in database): these graphs represent knowledge of the form "IF ... THEN." We present here an optimization of the natural forward chaining algorithm for CG rules. Generating a graph of rules dependencies makes the following sequences of rule applications far more efficient, and the structure of this graph can be used to obtain new decidability results.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.