An Improved Answer Set Program Splitting Method And Research On Program Simplification

Artificial intelligence is a very important subject in computer science. The knowledge representation and reasoning in artificial intelligence aims at completing and reflecting human intelligence in computer through the understanding of intelligence and cognitive nature. Non-monotonic logic is the mainstream tool of knowledge representation and reasoning. In this dissertation, the answer set programming(ASP) which we studied is an import content of non-monotonic logic.With many years development of answer set programming problems, its theory and solver has been relatively mature. However, the main development focus in answer set program is still solver efficiency.In the process of ASP solver speeding up development, Lifschitz and Turner proposed the concept of splitting set and program splitting in 1994. Moreover,they provided a method to divide a logic program into two parts which was named as bottom and top, and showed that the task of computing the answer sets of the program can be converted into the tasks of computing the answer sets of these parts. The concept of splitting set and program splitting brought new ideas to speed up solving answer sets of ASP program. In the subsequent period,splitting set and program splitting have been promoted and recognized continuously. However, the notion of splitting set which proposed by Lifschitz and Turner was based on tough conditions. Because of this, the empty set and the set of all atoms are the only two splitting sets for many ASP programs in the actual situation. These two splitting sets made no sense to speed up the answer sets solving in ASP programs, because these splitting sets cannot divide programs by the splitting methods.This dissertation will discuss and research about Lifschitz and Turner’s splitting set and program splitting theorem. The main achievements obtained in this dissertation are shown as following details.Firstly, this dissertation extends Lifschitz and Turner’s splitting set and program splitting theorem to allow the program to be split by an arbitrary set of atoms and introduce a new program splitting method for NLP. After this, this dissertation extends this result to DLP and propose the strong splitting method.As the splitting set can be an arbitrary set of atoms, the applicability of program splitting can be extended greatly.Secondly, this dissertation figures out the main performance bottlenecks through analyzing properties of the new splitting method and puts forward the improved scheme. Moreover, the data coming from experiment in this dissertation support the fact that using arbitrary set of atoms as splitting set and the new splitting method to divide ASP program and solve its answer sets is quicker than solve directly. More precisely, it is two to three times faster than the original according the experiment.Thirdly, during analyzing how the new splitting set effect on the performance of new splitting method, this dissertation finds out that if atoms in the splitting set are satisfied by every answer set of the program, it could release the computational complexity of answer set solving. According to this, this dissertation extends the usage of splitting set to program simplification. In the same words, we can use consequence of the ASP programs to simplify themselves. The purpose of program simplification is still to speed up solving answer sets of ASP program.This dissertation proposes the new splitting set and new splitting method to make contribution to speed up solving answer sets of ASP program which brings a substantial progress, and extends the concept of splitting set to practical application such as program simplification. All these bring new ideas to improve solving ASP program.