---
title: "Eliminating Disjunctions in Answer Set Programming by Restricted Unfolding"
authors:
  - "Jian-Min Ji"
  - "Hai Wan"
  - "Kewen Wang"
  - "Zhe Wang"
  - "Chuhan Zhang"
  - "Jiangtao Xu"
doi: ""
url: "https://ijcai.org/proceedings/2016/164"
pdf: "https://ijcai.org/proceedings/2016/0164.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "1130-1136"
track: ""
keywords:
---

# Eliminating Disjunctions in Answer Set Programming by Restricted Unfolding

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

*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.