Abstract
Boolean functions in Answer Set Programming have proven a useful modelling tool. They are usually specified by means of aggregates or external atoms. A crucial step in computing answer sets for logic programs containing Boolean functions is verifying whether partial interpretations satisfy a Boolean function for all possible values of its undefined atoms. In this paper, we develop a new methodology for showing when such checks can be done in deterministic polynomial time. This provides a unifying view on all currently known polynomialtime decidability results, and furthermore identifies promising new classes that go well beyond the state of the art. Our main technique consists of using an ordering on the atoms to significantly reduce the necessary number of model checks. For many standard aggregates, we show how this ordering can be automatically obtained.
Original language | English |
---|---|
Title of host publication | 30th AAAI Conference on Artificial Intelligence, AAAI 2016 |
Publisher | AAAI press |
Pages | 879-885 |
Number of pages | 7 |
ISBN (Electronic) | 9781577357605 |
Publication status | Published - 2016 |
Event | 30th Association for the Advancement of Artificial Intelligence Conference - Phoenix, United States Duration: 12 Feb 2016 → 17 Feb 2016 Conference number: 30 |
Conference
Conference | 30th Association for the Advancement of Artificial Intelligence Conference |
---|---|
Abbreviated title | AAAI 2016 |
Country/Territory | United States |
City | Phoenix |
Period | 12/02/16 → 17/02/16 |