Effectively solving NP-SPEC encodings by translation to ASP

Mario Alviano, Wolfgang Faber

Research output: Contribution to journalArticle

Abstract

NP-SPEC is a language for specifying problems in NP in a declarative way. Despite the fact that the semantics of the language was given by referring to Datalog with circumscription, which is very close to answer set programming (ASP), so far the only existing implementations are by means of Prolog and via Boolean satisfiability solvers. In this paper, we present translations from NP-SPEC to ASP, and provide an experimental evaluation of existing implementations and the proposed translations into ASP using various ASP solvers. The results show that translating into ASP clearly has an edge over the existing translation into SAT, which involves an intrinsic grounding process. We also argue that it might be useful to incorporate certain language constructs of NP-SPEC into mainstream ASP.

Original languageEnglish
Pages (from-to)577-601
Number of pages25
JournalJournal of Experimental and Theoretical Artificial Intelligence
Volume27
Issue number5
DOIs
Publication statusPublished - 3 Sep 2015

Fingerprint

Answer Set Programming
Electric grounding
Encoding
Semantics
Boolean Satisfiability
Datalog
Prolog
Experimental Evaluation
Language

Cite this

@article{f73bb17efca8409681ba81a29bb15aa2,
title = "Effectively solving NP-SPEC encodings by translation to ASP",
abstract = "NP-SPEC is a language for specifying problems in NP in a declarative way. Despite the fact that the semantics of the language was given by referring to Datalog with circumscription, which is very close to answer set programming (ASP), so far the only existing implementations are by means of Prolog and via Boolean satisfiability solvers. In this paper, we present translations from NP-SPEC to ASP, and provide an experimental evaluation of existing implementations and the proposed translations into ASP using various ASP solvers. The results show that translating into ASP clearly has an edge over the existing translation into SAT, which involves an intrinsic grounding process. We also argue that it might be useful to incorporate certain language constructs of NP-SPEC into mainstream ASP.",
keywords = "answer set programming, declarative programming, knowledge representation, NP-SPEC",
author = "Mario Alviano and Wolfgang Faber",
year = "2015",
month = "9",
day = "3",
doi = "10.1080/0952813X.2014.993505",
language = "English",
volume = "27",
pages = "577--601",
journal = "Journal of Experimental and Theoretical Artificial Intelligence",
issn = "0952-813X",
publisher = "Taylor and Francis Ltd.",
number = "5",

}

Effectively solving NP-SPEC encodings by translation to ASP. / Alviano, Mario; Faber, Wolfgang.

In: Journal of Experimental and Theoretical Artificial Intelligence, Vol. 27, No. 5, 03.09.2015, p. 577-601.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Effectively solving NP-SPEC encodings by translation to ASP

AU - Alviano, Mario

AU - Faber, Wolfgang

PY - 2015/9/3

Y1 - 2015/9/3

N2 - NP-SPEC is a language for specifying problems in NP in a declarative way. Despite the fact that the semantics of the language was given by referring to Datalog with circumscription, which is very close to answer set programming (ASP), so far the only existing implementations are by means of Prolog and via Boolean satisfiability solvers. In this paper, we present translations from NP-SPEC to ASP, and provide an experimental evaluation of existing implementations and the proposed translations into ASP using various ASP solvers. The results show that translating into ASP clearly has an edge over the existing translation into SAT, which involves an intrinsic grounding process. We also argue that it might be useful to incorporate certain language constructs of NP-SPEC into mainstream ASP.

AB - NP-SPEC is a language for specifying problems in NP in a declarative way. Despite the fact that the semantics of the language was given by referring to Datalog with circumscription, which is very close to answer set programming (ASP), so far the only existing implementations are by means of Prolog and via Boolean satisfiability solvers. In this paper, we present translations from NP-SPEC to ASP, and provide an experimental evaluation of existing implementations and the proposed translations into ASP using various ASP solvers. The results show that translating into ASP clearly has an edge over the existing translation into SAT, which involves an intrinsic grounding process. We also argue that it might be useful to incorporate certain language constructs of NP-SPEC into mainstream ASP.

KW - answer set programming

KW - declarative programming

KW - knowledge representation

KW - NP-SPEC

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

U2 - 10.1080/0952813X.2014.993505

DO - 10.1080/0952813X.2014.993505

M3 - Article

VL - 27

SP - 577

EP - 601

JO - Journal of Experimental and Theoretical Artificial Intelligence

JF - Journal of Experimental and Theoretical Artificial Intelligence

SN - 0952-813X

IS - 5

ER -