Complexities of Homomorphism and Isomorphism for Definite Logic Programs  

作　　者：许道云 陶志红 

机构地区：[1]Department of Computer Science, Guizhou University, Guiyang 550025, P.R. China [2]Department of Computer Science, Peking University, Beijing 100871, P.R. China

出　　处：《Journal of Computer Science & Technology》2005年第6期758-762,共5页计算机科学技术学报（英文版）

基　　金：国家自然科学基金，the Special Foundation for Improving Scientific Research Condition of Guizhou, and the Government Foundation of Guizhou Province，the Government Foundation of Guizhou Province

摘　　要：A homomorphism φ of logic programs from P to P＇ is a function mapping Atoms（P） to Atoms（P＇） and it preserves complements and program clauses. For each definite program clause a ← a1,...,an ∈ P it implies that φ（a） ←- φ（a1）,...,φ（an） is a program clause of P＇. A homomorphism φis an isomorphism if φ 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）.A homomorphism φ of logic programs from P to P＇ is a function mapping Atoms（P） to Atoms（P＇） and it preserves complements and program clauses. For each definite program clause a ← a1,...,an ∈ P it implies that φ（a） ←- φ（a1）,...,φ（an） is a program clause of P＇. A homomorphism φis an isomorphism if φ 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）.

关 键 词：logic program HOMOMORPHISM ISOMORPHISM decision problem COMPLEXITY 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]