DOI:
Abstract:
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.