Graph-Based Knowledge Representation - Chein, Michel

. .

Résumé :
This book provides a de?nition and study of a knowledge representation and r- soning formalism stemming from conceptual graphs, while focusing on the com- tational properties of this formalism. Knowledge can be symbolically represented in many ways. The knowledge representation and reasoning formalism presented here is a graph formalism - knowledge is represented by labeled graphs, in the graph theory sense, and r- soning mechanisms are based on graph operations, with graph homomorphism at the core. This formalism can thus be considered as related to semantic networks. Since their conception, semantic networks have faded out several times, but have always returned to the limelight. They faded mainly due to a lack of formal semantics and the limited reasoning tools proposed. They have, however, always rebounded - cause labeled graphs, schemas and drawings provide an intuitive and easily und- standable support to represent knowledge. This formalism has the visual qualities of any graphic model, and it is logically founded. This is a key feature because logics has been the foundation for knowledge representation and reasoning for millennia. The authors also focus substantially on computational facets of the presented formalism as they are interested in knowledge representation and reasoning formalisms upon which knowledge-based systems can be built to solve real problems. Since object structures are graphs, naturally graph homomorphism is the key underlying notion and, from a computational viewpoint, this moors calculus to combinatorics and to computer science domains in which the algorithmicqualitiesofgraphshavelongbeenstudied,asindatabasesandconstraint networks.

Sommaire:
Introduction (Knowledge Representation and Reasoning, Conceptual Graphs, A Graph-Based Approach to KR).-Basic Conceptual Graphs (Homomorphism, Subsumption Preorder, Irredundant BGs, Generalization and Specialization Operations, Normal BGs, Computational Complexity of Basic Problems).-Simple Conceptual Graphs (Generalization and Specialization Operations, Standard and Normal SGs, Coref-Homomorphism, Antinormal Form).- Formal Semantics of SGs (Model and FOL semantics, Soundness and Completeness of (coref) Homomorphism, Positive Conjunctive and Existential Fragment of FOL, Description Logics and Conceptual Graphs).- BG Homomorphism and Equivalent Notions (Conceptual Hypergraphs, Graphs, Relational Structures, Conjunctive Queries, Constraint Satisfaction Problem).- Basic Algorithms for BG Homomorphism (Backtrack Algorithms, Constraint Processing, Label Comparison).- Tractable Cases (Tractability Based on the Multigraph-Acyclicity of the Source BG, Tractability Based on the Hypergraph-Acyclicity of the Source BG, the Existential Conjunctive Guarded Fragment, Generalizations of Graph-Acyclicity and Hypergraph-Acyclicity).- Other Specialization/Generalization Operations (The Least Generalization and Greatest Specialization of two BGs, Maximal Join, Compatible Partitions and Extended Join, Type Expansion and Contraction).- Nested Conceptual Graphs (Nested Graphs, Logical Semantics, Soundness and Completeness).- Rules (Graph rules, Logical Semantics, Forward Chaining, Backward Chaining, Soundness and Completeness, Computational Complexity).- The BG Family (Deduction problems with Facts, Rules and Constraints, Computational Complexity).- Conceptual Graphs with Negation (Full Conceptual Graphs, Logical Semantics, Calculus, Atomic Negation, Coreference and Difference, Computational Complexity).- An Application of Nested Typed Graphs: Semantic Anotation Bases.- Mathematical Background.- References.- Index

From the reviews: This well-written book is a wonderful text for researchers working on theoretical artificial intelligence (AI). Fundamentally, AI represents knowledge with mathematical objects and then designs computational rules to manipulate these objects. ... In summary, this is a theoretical book for a graph-based approach to knowledge representation. ... A number of detailed algorithms presented in the book may serve as good references for designing a variety of AI systems, such as database mining and logic reasoning. (Hsun-Hsien Chang, ACM Computing Reviews, April, 2009)