Based On The Phase Change Question Of The Answer Set Logic Program

Logic program based on answer set semantics(or stable model)(Answer Set Program,ASP),is a kind of descriptive paradigm.Because of its essential characteristics of non-monotone and the various effective answer set solver of the system emergence,it is widely applied to intelligent planning,diagnosis,scheduling,etc.Phase transition is an important method to study the properties of complex systems,and it has obtained profound theoretical results in the aspects of satisfiability problems(SAT)and formal logic procedures.The complexity of the existence of the answer set of disjunction logic program(DLP)is higher than the normal logic program in the polynomial layer.In this paper,the phase transition properties of the logic program are studied,mainly including:Proved that any disjunction logic program model equivalent to the syntactic simple disjunction logic programs,that is to say,to any disjunction logic program P,there is a disjunction logic programming Q,in which all the rules of the head(at most)contains two atoms,rule(at most)contains two literals in the body.On a set of atoms that are limited to P,P and Q have the same answer.(2)Proved the existence of the answer set of maximum disjunction logic programs with at most two atoms in the rule head.If the number of literals in the rule body is greater than 1,the maximum logical program has no answer set,otherwise,the maximum logical program has n answer sets,and the size of any answer set is n-1.(3)Learned the kernel property of graph,it is determined whether the logic program exists an answer set with an energy function.By solving the basic function of the energy function,It can be judged whether the logic program has the answer.(4)The experimental results showed that: If(27)(27)10 ratio(the ratio of negative literals in the rules of disjunction logic program is expressed as ratio),as the nm / value increases,theproposition of program existing an answer set quickly goes from 1 to 0 at the key point,the phase transition occurs;As m/n increases,the number of loops needed to solve the answer set is stable,equal to the number of variables in the program.Ifratio(28)1,the answer set probability will be a "depression" phenomenon with the increasing ofnm /,which we call "first half phase transition",and the claspD solver is faster than cmodels solver.Where m and n are means the number of rules and atoms in logic program,respectively.