On Elementary Loops and Proper Loops for Disjunctive Logic Programs


  • Jianmin Ji University of Science and Technology of China
  • Hai Wan Sun Yat-Sen University
  • Peng Xiao Sun Yat-Sen University




Elementary Loops, Proper Loops, Disjunctive Logic Programs


This paper proposes an alternative definition of elementary loops and extends the notion of proper loops for disjunctive logic programs. Different from normal logic programs, the computational complexities of recognizing elementary loops and proper loops for disjunctive programs are coNP-complete. To address this problem, we introduce weaker versions of both elementary loops and proper loops and provide polynomial time algorithms for identifying them respectively. On the other hand, based on the notion of elementary loops, the class of Head-Elementary-loop-Free (HEF) programs was presented, which can be turned into equivalent normal logic programs by shifting head atoms into bodies. However, the problem of recognizing an HEF program is coNP-complete. Then we present a subclass of HEF programs which generalizes the class of Head-Cycle-Free programs and provide a polynomial time algorithm to identify them. At last, some experiments show that both elementary loops and proper loops could be replaced by their weak versions in practice.




How to Cite

Ji, J., Wan, H., & Xiao, P. (2015). On Elementary Loops and Proper Loops for Disjunctive Logic Programs. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9397



AAAI Technical Track: Knowledge Representation and Reasoning