Graph-based knowledge representation. Computational foundations of conceptual graphs (Q932109)

This book provides an introduction and study of conceptual graphs and their applications for knowledge representation. The authors present the theoretical basis of this formalism. They develop the mathematical framework for graph-based knowledge representation focusing on computational properties of this approach. However, the book does not give a methodology for knowledge representation nor present actual applications. The book consists of three parts and an appendix. The first part introduces the core notions like basic and simple conceptual graphs and the corresponding homomorphisms. It also presents soundness and completeness of homomorphism with respect to entailment and first-order logical deduction. The second part of the book is devoted to computational aspects of conceptual graphs. It develops algorithms for homomorphisms and studies special cases that allow for tractable (polynomial) solutions. The third part deals with extension of the basic notions such as nested conceptual graphs, rules, constraints, and negation. The appendix summarizes the mathematical notions used in the book. The book includes many notes with additional information and lots of pointers to further reading. It also examines the relation of the concepts under consideration to other domains and approaches. For instance, there is a discussion about the relationship of conceptual graphs and description logics. The appendix is sometimes a bit too short. For example, it introduces the complexity classes P and NP in one sentence each. This could be OK if not more was needed in the book. Moreover, there are theorems stating that some problems are \(\Pi^p_2\)-complete. Thus the appendix should explain what `completeness' means in this context and also sketch the polynomial hierarchy.