Graph-based Knowledge Representation - Computational Foundations of Conceptual Graphs

Preface

Contents

Introduction

1.1 Knowledge Representation and Reasoning

1.2 Conceptual Graphs

1.3 A Graph-Based Approach to KR

Part I Foundations: Basic and Simple Conceptual Graphs

Basic Conceptual Graphs

2.1 Definition of Basic Conceptual Graphs (BGs)

2.2 BG Homomorphism

2.3 BG Subsumption Properties

2.4 Generalization and Specialization Operations

2.5 Normal BGs

2.6 Complexity of Basic Problems

2.7 Bibliographic Notes

Simple Conceptual Graphs

3.1 Introduction

3.2 Vocabulary

3.3 Simple Conceptual Graphs (SGs)

3.4 Generalization and Specialization Operations

3.5 Standard and Normal SGs

3.6 Coref-Homomorphism

3.7 Antinormal Form and Homomorphism

3.8 Bibliographic Notes

Formal Semantics of SGs

4.1 Model Semantic

4.2 Logical Semantic

4.3 Positive, Conjunctive, and Existential Fragment of FOL

4.4 Note on the Relationships Between Description Logics

and Conceptual Graphs

4.5 Bibliographic Notes

BG Homomorphism and Equivalent Notions

5.1 Conceptual Graphs and Conceptual Hypergraphs

5.2 Graphs

5.3 Relational Structures and Databases

5.4 Constraint Satisfaction Problem

5.5 Bibliographic Notes

Part II Computational Aspects of Basic Conceptual Graphs

Basic Algorithms for BG Homomorphism

6.1 Algorithms for BG Homomorphisms

6.2 Constraint Processing

6.3 Label Comparison

6.4 Bibliographic Notes

Tractable Cases

7.1 Introduction

7.2 Tractability Based on the Multigraph-Acyclicity

of the Source BG

7.3 Tractability Based on the Hypergraph-Acyclicity

of the Source BG

7.4 Generalizations of Graph-Acyclicity

and Hypergraph-Acyclicity

7.5 What About Labels?

7.6 Complementary Notes

Other Specialization/Generalization Operations

8.1 The Least Generalization and Greatest Specialization of Two

BGs

8.2 Basic Compatibility Notions and Maximal Joins

8.3 Compatible Partitions and Extended Join

8.4 G-Specializations

8.5 Type Expansion and Contraction

8.6 Bibliographic Notes

Part III Extensions

Nested Conceptual Graphs

9.1 Introduction

9.2 Nested Basic Graphs (NBGs)

9.3 Nested Graphs (NGs)

9.4 Nested Typed Graphs

9.5 The Semantics

9.6 Representation of Nested Typed Graphs by BGs

9.7 Bibliographic Notes

Rules

10.1 Definition and Logical Semantics of a Rule

10.2 Forward Chaining

10.3 Backward Chaining

10.4 Computational Complexity of FR-

with Rules

10.5 Bibliographic Notes

The BG Family: Facts, Rules and Constraints

11.1 Overview of the BG Family

11.2 FC: Facts and Constraints

11.3 Combining Rules and Constraints

11.4 Complexity in FRC/FEC/

for Particular Cases of

Rules and Constraints

11.5 Bibliographic Notes

Conceptual Graphs with Negation

12.1 Full Conceptual Graphs

12.2 Conceptual Graphs with Atomic Negation

12.3 Bibliographic Notes

An Application of Nested Typed Graphs: Semantic Annotation Bases

13.1 Annotation

13.2 Annotation Base

13.3 Querying an Annotation Base

13.4 Annotation and the SemanticWeb

13.5 Conclusion

Mathematical Background

A.1 Sets and Relations

A.2 Graphs

A.3 Ordered Sets

A.4 First Order Logic (FOL)

A.5 Algorithm and Problem Complexity

References

Index