Madalina Croitoru, Ernesto Compatangelo
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.
Subjects: 11. Knowledge Representation; 3. Automated Reasoning
Submitted: Mar 3, 2006