Graph-based Knowledge Representation (eBook)

Computational Foundations of Conceptual Graphs

Michel Chein, Marie-Laure Mugnier (Autoren)

eBook Download: PDF

2008 | 2009
XIV, 428 Seiten
Springer London (Verlag)
978-1-84800-286-9 (ISBN)

Infos

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.

Inhalt

Preface 5
Contents 9
Introduction 15
1.1 Knowledge Representation and Reasoning 15
1.2 Conceptual Graphs 22
1.3 A Graph-Based Approach to KR 27
Part I Foundations: Basic and Simple Conceptual Graphs 32
Basic Conceptual Graphs 33
2.1 Definition of Basic Conceptual Graphs (BGs) 34
2.2 BG Homomorphism 42
2.3 BG Subsumption Properties 47
2.4 Generalization and Specialization Operations 52
2.5 Normal BGs 61
2.6 Complexity of Basic Problems 66
2.7 Bibliographic Notes 68
Simple Conceptual Graphs 70
3.1 Introduction 71
3.2 Vocabulary 73
3.3 Simple Conceptual Graphs (SGs) 77
3.4 Generalization and Specialization Operations 80
3.5 Standard and Normal SGs 82
3.6 Coref-Homomorphism 83
3.7 Antinormal Form and Homomorphism 87
3.8 Bibliographic Notes 91
Formal Semantics of SGs 93
4.1 Model Semantic 94
4.2 Logical Semantic 99
4.3 Positive, Conjunctive, and Existential Fragment of FOL 102
4.4 Note on the Relationships Between Description Logics 110
and Conceptual Graphs 110
4.5 Bibliographic Notes 114
BG Homomorphism and Equivalent Notions 115
5.1 Conceptual Graphs and Conceptual Hypergraphs 117
5.2 Graphs 123
5.3 Relational Structures and Databases 129
5.4 Constraint Satisfaction Problem 134
5.5 Bibliographic Notes 142
Part II Computational Aspects of Basic Conceptual Graphs 143
Basic Algorithms for BG Homomorphism 144
6.1 Algorithms for BG Homomorphisms 144
6.2 Constraint Processing 160
6.3 Label Comparison 170
6.4 Bibliographic Notes 178
Tractable Cases 180
7.1 Introduction 180
7.2 Tractability Based on the Multigraph-Acyclicity 183
of the Source BG 183
7.3 Tractability Based on the Hypergraph-Acyclicity 194
of the Source BG 194
7.4 Generalizations of Graph-Acyclicity 207
and Hypergraph-Acyclicity 207
7.5 What About Labels? 211
7.6 Complementary Notes 213
Other Specialization/Generalization Operations 215
8.1 The Least Generalization and Greatest Specialization of Two 216
BGs 216
8.2 Basic Compatibility Notions and Maximal Joins 220
8.3 Compatible Partitions and Extended Join 230
8.4 G-Specializations 236
8.5 Type Expansion and Contraction 243
8.6 Bibliographic Notes 250
Part III Extensions 252
Nested Conceptual Graphs 253
9.1 Introduction 254
9.2 Nested Basic Graphs (NBGs) 255
9.3 Nested Graphs (NGs) 262
9.4 Nested Typed Graphs 264
9.5 The Semantics 268
9.6 Representation of Nested Typed Graphs by BGs 273
9.7 Bibliographic Notes 276
Rules 279
10.1 Definition and Logical Semantics of a Rule 279
10.2 Forward Chaining 284
10.3 Backward Chaining 297
10.4 Computational Complexity of FR- 307
with Rules 307
10.5 Bibliographic Notes 313
The BG Family: Facts, Rules and Constraints 316
11.1 Overview of the BG Family 316
11.2 FC: Facts and Constraints 318
11.3 Combining Rules and Constraints 326
11.4 Complexity in FRC/FEC/ 332
for Particular Cases of 332
Rules and Constraints 332
11.5 Bibliographic Notes 339
Conceptual Graphs with Negation 341
12.1 Full Conceptual Graphs 342
12.2 Conceptual Graphs with Atomic Negation 354
12.3 Bibliographic Notes 379
An Application of Nested Typed Graphs: Semantic Annotation Bases 381
13.1 Annotation 381
13.2 Annotation Base 385
13.3 Querying an Annotation Base 389
13.4 Annotation and the SemanticWeb 392
13.5 Conclusion 394
Mathematical Background 396
A.1 Sets and Relations 397
A.2 Graphs 400
A.3 Ordered Sets 406
A.4 First Order Logic (FOL) 409
A.5 Algorithm and Problem Complexity 413
References 415
Index 424

Produkt-Details

• Erscheint lt. Verlag: 20.10.2008
• Reihe/Serie: Advanced Information and Knowledge Processing
• Reihe/Serie: Advanced Information and Knowledge Processing
• Zusatzinfo: XIV, 428 p.
• Verlagsort: London
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Datenbanken
• Themenwelt: Mathematik / Informatik ► Informatik ► Netzwerke
• Themenwelt: Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Graphentheorie
• Themenwelt: Technik
• Schlagworte: algorithms • Conceptual Graphs • Graph • graph theory • Hypergraph • Knowledge Representation • Reasoning • SiM
• ISBN-10: 1-84800-286-6 / 1848002866
• ISBN-13: 978-1-84800-286-9 / 9781848002869