Boolean functions with ordered domains in answer set programming

Mario Alviano, Wolfgang Faber, Hannes Strass

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

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 languageEnglish
Title of host publication30th AAAI Conference on Artificial Intelligence, AAAI 2016
PublisherAAAI press
Pages879-885
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

Conference

Conference30th Association for the Advancement of Artificial Intelligence Conference
Abbreviated titleAAAI 2016
CountryUnited States
CityPhoenix
Period12/02/1617/02/16

Fingerprint

Boolean functions
Atoms
Computability and decidability
Polynomials

Cite this

Alviano, M., Faber, W., & Strass, H. (2016). Boolean functions with ordered domains in answer set programming. In 30th AAAI Conference on Artificial Intelligence, AAAI 2016 (pp. 879-885). AAAI press.
Alviano, Mario ; Faber, Wolfgang ; Strass, Hannes. / Boolean functions with ordered domains in answer set programming. 30th AAAI Conference on Artificial Intelligence, AAAI 2016. AAAI press, 2016. pp. 879-885
@inproceedings{307c5436667b4d80894320e3dc1fde20,
title = "Boolean functions with ordered domains in answer set programming",
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.",
author = "Mario Alviano and Wolfgang Faber and Hannes Strass",
year = "2016",
language = "English",
pages = "879--885",
booktitle = "30th AAAI Conference on Artificial Intelligence, AAAI 2016",
publisher = "AAAI press",

}

Alviano, M, Faber, W & Strass, H 2016, Boolean functions with ordered domains in answer set programming. in 30th AAAI Conference on Artificial Intelligence, AAAI 2016. AAAI press, pp. 879-885, 30th Association for the Advancement of Artificial Intelligence Conference, Phoenix, United States, 12/02/16.

Boolean functions with ordered domains in answer set programming. / Alviano, Mario; Faber, Wolfgang; Strass, Hannes.

30th AAAI Conference on Artificial Intelligence, AAAI 2016. AAAI press, 2016. p. 879-885.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Boolean functions with ordered domains in answer set programming

AU - Alviano, Mario

AU - Faber, Wolfgang

AU - Strass, Hannes

PY - 2016

Y1 - 2016

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

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

UR - http://www.scopus.com/inward/record.url?scp=85007210832&partnerID=8YFLogxK

UR - https://aaai.org/Press/Proceedings/aaai16.php

M3 - Conference contribution

SP - 879

EP - 885

BT - 30th AAAI Conference on Artificial Intelligence, AAAI 2016

PB - AAAI press

ER -

Alviano M, Faber W, Strass H. Boolean functions with ordered domains in answer set programming. In 30th AAAI Conference on Artificial Intelligence, AAAI 2016. AAAI press. 2016. p. 879-885