Eliminating Disjunctions in Answer Set Programming by Restricted Unfolding

Ji, Jian-Min; Wan, Hai; Wang, Kewen; Wang, Zhe; Zhang, Chuhan; Xu, Jiangtao

Eliminating Disjunctions in Answer Set Programming by Restricted Unfolding

Jian-Min Ji, Hai Wan, Kewen Wang, Zhe Wang, Chuhan Zhang, Jiangtao Xu

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 1130-1136.

Abstract

A disjunctive logic program under the answer set semantics can be equivalently translated to a normal logic program by the shifting transformation, if the program is head-cycle-free. In this paper, we provide an answer-set-preserving rewriting of a general disjunctive program to a normal program by first applying the unfolding transformation on atoms that prevent the program from being head-cycle-free, then shifting the resulting program. Different from other transformations that eliminate disjunctions in answer set programming, the new rewriting is efficient for almost head-cycle-free programs, i.e., programs that have only a few atoms that prevent them to be head-cycle-free. Based on the new rewriting, we provide an anytime algorithm to compute answer sets of a disjunctive program by calling solvers for normal logic programs. The experiment shows that the algorithm is efficient for some disjunctive programs. We also extend the rewriting to non-ground answer set programs on finite structures.

Jian-Min Ji, Hai Wan, Kewen Wang, Zhe Wang, Chuhan Zhang, and Jiangtao Xu. 2016. Eliminating Disjunctions in Answer Set Programming by Restricted Unfolding. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 1130–1136. https://ijcai.org/proceedings/2016/164

@inproceedings{ijcai2016p164,
  title     = {Eliminating Disjunctions in Answer Set Programming by Restricted Unfolding},
  author    = {Ji, Jian-Min and Wan, Hai and Wang, Kewen and Wang, Zhe and Zhang, Chuhan and Xu, Jiangtao},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {1130--1136},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/164},
}

TY  - CPAPER
TI  - Eliminating Disjunctions in Answer Set Programming by Restricted Unfolding
AU  - Ji, Jian-Min
AU  - Wan, Hai
AU  - Wang, Kewen
AU  - Wang, Zhe
AU  - Zhang, Chuhan
AU  - Xu, Jiangtao
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 1130
EP  - 1136
UR  - https://ijcai.org/proceedings/2016/164
ER  -