%0 Journal Article
%T Complexities of Homomorphism and Isomorphism for Definite Logic Programs
%A Dao-Yun Xu
%A Zhi-Hong Tao
%A <br>Dao-Yun Xu
%A and Zhi-Hong Tao
%J 计算机科学技术学报
%D 2005
%I 
%X A homomorphism φ 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 ← a1, ..., an ∈ P it implies that φ(a) ← φ(a1), ..., φ(an) is a program clauses 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). The work is supported by the National Natural Science Foundation of China (Grant Nos. 60310213 and 60463001), the Special Foundation for Improving Scientific Research Condition of Guizhou, and the Government Foundation of Guizhou Province.
%K logic program
%K homomorphism
%K isomorphism
%K decision problem
%K complexity<br>计算技术
%K 逻辑规划
%K 同形结构
%K 复杂性
%K 函数映射
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=B70ED867C8B90582639CA6E3BD959391&yid=2DD7160C83D0ACED&vid=A04140E723CB732E&iid=B31275AF3241DB2D&sid=3D8AB54CA690066A&eid=1CBB73E9593E8833&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=18