A Tree Decomposition Algorithm for Conceptual Graph Projection

Principles of Knowledge Representation and Reasoning: Proceedings of the Tenth International Conference (KR2006)

Volume

Principles of Knowledge Representation and Reasoning: Proceedings of the Tenth International Conference (KR2006)

Contents

This paper discusses combinatorial mechanisms for reasoning with conceptual graphs. We focus on the combinatorial aspects of a backtracking approach to the NP-hard problem of projection, which is the main tool for reasoning with conceptual graphs. We use effective graph-theoretical look-ahead procedures, based on a conceptual forest decomposition of the graph to be projected. We believe that our approach to projection can improve the practical applicability of exponential algorithms currently used to solve NP-hard problems.