Elementary Loops Revisited


  • Jianmin Ji University of Science and Technology of China
  • Hai Wan Sun Yat-sen University
  • Peng Xiao Sun Yat-sen University
  • Ziwei Huo Sun Yat-sen University
  • Zhanhao Xiao Sun Yat-sen University




Answer Set Programming, Elementary Loops, Dependency Graphs


The notions of loops and loop formulas play an important role in answer set computation. However, there would be an exponential number of loops in the worst case. Gebser and Schaub characterized a subclass elementary loops and showed that they are sufficient for selecting answer sets from models of a logic program. This paper proposes an alternative definition of elementary loops and identify a subclass of elementary loops, called proper loops. By applying a special form of their loop formulas, proper loops are also sufficient for the SAT-based answer set computation. A polynomial algorithm to recognize a proper loop is given and shows that for certain logic programs, identifying all proper loops of a program is more efficient than that of elementary loops. Furthermore, we prove that, by considering the structure of the positive body-head dependency graph of a program, a large number of loops could be ignored for identifying proper loops. We provide another algorithm for identifying all proper loops of a program. The experiments show that, for certain programs whose dependency graphs consisting of sets of components that are densely connected inside and sparsely connected outside, the new algorithm is more efficient.




How to Cite

Ji, J., Wan, H., Xiao, P., Huo, Z., & Xiao, Z. (2014). Elementary Loops Revisited. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8864



AAAI Technical Track: Knowledge Representation and Reasoning