https://hal.inria.fr/hal-00918126Baget, Jean-FrançoisJean-FrançoisBagetEXMO - Computer mediated exchange of structured knowledge - Inria Grenoble - Rhône-Alpes - Inria - Institut National de Recherche en Informatique et en AutomatiqueImproving the Forward Chaining Algorithm for Conceptual Graphs RulesHAL CCSD2004[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI]Euzenat, Jérôme2013-12-12 22:34:072022-01-20 17:29:062013-12-16 15:41:14enConference papersapplication/pdf1Simple Conceptual 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.