Chein / Mugnier Graph-based Knowledge Representation

Computational Foundations of Conceptual Graphs
1. Auflage 2008
ISBN: 978-1-84800-286-9
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 428 Seiten

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.

Autoren/Hrsg.

Chein, Michel

Mugnier, Marie-Laure

Inhaltsverzeichnis

1;Preface;5
2;Contents;9
3;Introduction;15
3.1;1.1 Knowledge Representation and Reasoning;15
3.2;1.2 Conceptual Graphs;22
3.3;1.3 A Graph-Based Approach to KR;27
4;Part I Foundations: Basic and Simple Conceptual Graphs;32
4.1;Basic Conceptual Graphs;33
4.1.1;2.1 Definition of Basic Conceptual Graphs (BGs);34
4.1.2;2.2 BG Homomorphism;42
4.1.3;2.3 BG Subsumption Properties;47
4.1.4;2.4 Generalization and Specialization Operations;52
4.1.5;2.5 Normal BGs;61
4.1.6;2.6 Complexity of Basic Problems;66
4.1.7;2.7 Bibliographic Notes;68
4.2;Simple Conceptual Graphs;70
4.2.1;3.1 Introduction;71
4.2.2;3.2 Vocabulary;73
4.2.3;3.3 Simple Conceptual Graphs (SGs);77
4.2.4;3.4 Generalization and Specialization Operations;80
4.2.5;3.5 Standard and Normal SGs;82
4.2.6;3.6 Coref-Homomorphism;83
4.2.7;3.7 Antinormal Form and Homomorphism;87
4.2.8;3.8 Bibliographic Notes;91
4.3;Formal Semantics of SGs;93
4.3.1;4.1 Model Semantic;94
4.3.2;4.2 Logical Semantic;99
4.3.3;4.3 Positive, Conjunctive, and Existential Fragment of FOL;102
4.3.4;4.4 Note on the Relationships Between Description Logics;110
4.3.5;and Conceptual Graphs;110
4.3.6;4.5 Bibliographic Notes;114
4.4;BG Homomorphism and Equivalent Notions;115
4.4.1;5.1 Conceptual Graphs and Conceptual Hypergraphs;117
4.4.2;5.2 Graphs;123
4.4.3;5.3 Relational Structures and Databases;129
4.4.4;5.4 Constraint Satisfaction Problem;134
4.4.5;5.5 Bibliographic Notes;142
5;Part II Computational Aspects of Basic Conceptual Graphs;143
5.1;Basic Algorithms for BG Homomorphism;144
5.1.1;6.1 Algorithms for BG Homomorphisms;144
5.1.2;6.2 Constraint Processing;160
5.1.3;6.3 Label Comparison;170
5.1.4;6.4 Bibliographic Notes;178
5.2;Tractable Cases;180
5.2.1;7.1 Introduction;180
5.2.2;7.2 Tractability Based on the Multigraph-Acyclicity;183
5.2.3;of the Source BG;183
5.2.4;7.3 Tractability Based on the Hypergraph-Acyclicity;194
5.2.5;of the Source BG;194
5.2.6;7.4 Generalizations of Graph-Acyclicity;207
5.2.7;and Hypergraph-Acyclicity;207
5.2.8;7.5 What About Labels?;211
5.2.9;7.6 Complementary Notes;213
5.3;Other Specialization/Generalization Operations;215
5.3.1;8.1 The Least Generalization and Greatest Specialization of Two;216
5.3.2;BGs;216
5.3.3;8.2 Basic Compatibility Notions and Maximal Joins;220
5.3.4;8.3 Compatible Partitions and Extended Join;230
5.3.5;8.4 G-Specializations;236
5.3.6;8.5 Type Expansion and Contraction;243
5.3.7;8.6 Bibliographic Notes;250
6;Part III Extensions;252
6.1;Nested Conceptual Graphs;253
6.1.1;9.1 Introduction;254
6.1.2;9.2 Nested Basic Graphs (NBGs);255
6.1.3;9.3 Nested Graphs (NGs);262
6.1.4;9.4 Nested Typed Graphs;264
6.1.5;9.5 The Semantics;268
6.1.6;9.6 Representation of Nested Typed Graphs by BGs;273
6.1.7;9.7 Bibliographic Notes;276
6.2;Rules;279
6.2.1;10.1 Definition and Logical Semantics of a Rule;279
6.2.2;10.2 Forward Chaining;284
6.2.3;10.3 Backward Chaining;297
6.2.4;10.4 Computational Complexity of FR-;307
6.2.5;with Rules;307
6.2.6;10.5 Bibliographic Notes;313
6.3;The BG Family: Facts, Rules and Constraints;316
6.3.1;11.1 Overview of the BG Family;316
6.3.2;11.2 FC: Facts and Constraints;318
6.3.3;11.3 Combining Rules and Constraints;326
6.3.4;11.4 Complexity in FRC/FEC/;332
6.3.5;for Particular Cases of;332
6.3.6;Rules and Constraints;332
6.3.7;11.5 Bibliographic Notes;339
6.4;Conceptual Graphs with Negation;341
6.4.1;12.1 Full Conceptual Graphs;342
6.4.2;12.2 Conceptual Graphs with Atomic Negation;354
6.4.3;12.3 Bibliographic Notes;379
6.5;An Application of Nested Typed Graphs: Semantic Annotation Bases;381
6.5.1;13.1 Annotation;381
6.5.2;13.2 Annotation Base;385
6.5.3;13.3 Querying an Annotation Base;389
6.5.4;13.4 Annotation and the SemanticWeb;392
6.5.5;13.5 Conclusion;394
6.6;Mathematical Background;396
6.6.1;A.1 Sets and Relations;397
6.6.2;A.2 Graphs;400
6.6.3;A.3 Ordered Sets;406
6.6.4;A.4 First Order Logic (FOL);409
6.6.5;A.5 Algorithm and Problem Complexity;413
7;References;415
8;Index;424