Complexities of Homomorphism and Isomorphism for Definite Logic Programs

A homomorphism \varphi of logic programs from P to P' is a function mapping Atoms (P) to Atoms (P') and it preserves complements and program clause. For each definite program clause a\leftarrow a_1, \ldots, a_n\in P it implies that \varphi(a)\leftarrow \varphi(a_1), \ldots, \varphi(a_n) is a program clauses of P' . A homomorphism \varphi is an isomorphism if \varphi is a bijection. In this paper, the complexity of the decision problems on homomorphism and isomorphism for definite logic programs is studied. It is shown that the homomorphism problem ( HOM - LP ) for definite logic programs is NP --complete, and the isomorphism problem ( ISO - LP ) is equivalent to the graph isomorphism problem ( GI \,).