Boolean functions with ordered domains in answer set programming

Mario Alviano, Wolfgang Faber, Hannes Strass

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Citations (Scopus)


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 languageEnglish
Title of host publication30th AAAI Conference on Artificial Intelligence, AAAI 2016
PublisherAAAI press
Number of pages7
ISBN (Electronic)9781577357605
Publication statusPublished - 2016
Event30th Association for the Advancement of Artificial Intelligence Conference - Phoenix, United States
Duration: 12 Feb 201617 Feb 2016
Conference number: 30


Conference30th Association for the Advancement of Artificial Intelligence Conference
Abbreviated titleAAAI 2016
Country/TerritoryUnited States


Dive into the research topics of 'Boolean functions with ordered domains in answer set programming'. Together they form a unique fingerprint.

Cite this