Abstract
One of the most important constraints faced by the development of artificial intelligence systems is the limited computing power. The logic problems involved in the construction of artificial intelligence systems are most often NP-complete in terms of computational complexity. In the case of conceptual graphs, logical inference is based on the subsummation relation between conceptual graphs. In this paper, we use homomorphisms of conceptual graphs as a model for the subsummation relation. Therefore, the problems related to the existence of relations between two conceptual graphs such as homomorphisms, isomorphisms or generalization, specialization relations become fundamental problems. Although all these decision problems are, in general, NP-complex, they can be efficiently solved in many cases, by certain strategies, without making too much compromise in terms of generality. In this paper, we propose a method to find and manipulate homomorphisms of conceptual graphs based on the concept of finite automaton. Thus, using the finite automaton to recognize predicate homomorphisms and moving a large part of the complexity of finding a homomorphism to the knowledge base construction phase represents our main contribution in this work.