Eintrag weiter verarbeiten
Optimizing Answer Set Computation via Heuristic-Based Decomposition
Gespeichert in:
Zeitschriftentitel: | Theory and Practice of Logic Programming |
---|---|
Personen und Körperschaften: | , , |
In: | Theory and Practice of Logic Programming, 19, 2019, 4, S. 603-628 |
Format: | E-Article |
Sprache: | Englisch |
veröffentlicht: |
Cambridge University Press (CUP)
|
Schlagwörter: |
author_facet |
CALIMERI, FRANCESCO PERRI, SIMONA ZANGARI, JESSICA CALIMERI, FRANCESCO PERRI, SIMONA ZANGARI, JESSICA |
---|---|
author |
CALIMERI, FRANCESCO PERRI, SIMONA ZANGARI, JESSICA |
spellingShingle |
CALIMERI, FRANCESCO PERRI, SIMONA ZANGARI, JESSICA Theory and Practice of Logic Programming Optimizing Answer Set Computation via Heuristic-Based Decomposition Artificial Intelligence Computational Theory and Mathematics Hardware and Architecture Theoretical Computer Science Software |
author_sort |
calimeri, francesco |
spelling |
CALIMERI, FRANCESCO PERRI, SIMONA ZANGARI, JESSICA 1471-0684 1475-3081 Cambridge University Press (CUP) Artificial Intelligence Computational Theory and Mathematics Hardware and Architecture Theoretical Computer Science Software http://dx.doi.org/10.1017/s1471068419000036 <jats:title>Abstract</jats:title><jats:p>Answer Set Programming (ASP) is a purely declarative formalism developed in the field of logic programming and non-monotonic reasoning: computational problems are encoded by logic programs whose answer sets, corresponding to solutions, are computed by an ASP system. Different, semantically equivalent, programs can be defined for the same problem; however, performance of systems evaluating them might significantly vary. We propose an approach for automatically transforming an input logic program into an equivalent one that can be evaluated more efficiently. One can make use of existing tree-decomposition techniques for rewriting selected rules into a set of multiple ones; the idea is to guide and adaptively apply them on the basis of proper new heuristics, to obtain a smart rewriting algorithm to be integrated into an ASP system. The method is rather general: it can be adapted to any system and implement different preference policies. Furthermore, we define a set of new heuristics tailored at optimizing grounding, one of the main phases of the ASP computation; we use them in order to implement the approach into the ASP system<jats:italic>DLV</jats:italic>, in particular into its grounding subsystem<jats:italic>ℐ-DLV</jats:italic>, and carry out an extensive experimental activity for assessing the impact of the proposal.</jats:p> Optimizing Answer Set Computation via Heuristic-Based Decomposition Theory and Practice of Logic Programming |
doi_str_mv |
10.1017/s1471068419000036 |
facet_avail |
Online |
finc_class_facet |
Informatik Mathematik Technik |
format |
ElectronicArticle |
fullrecord |
blob:ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTAxNy9zMTQ3MTA2ODQxOTAwMDAzNg |
id |
ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTAxNy9zMTQ3MTA2ODQxOTAwMDAzNg |
institution |
DE-Gla1 DE-Zi4 DE-15 DE-Rs1 DE-Pl11 DE-105 DE-14 DE-Ch1 DE-L229 DE-D275 DE-Bn3 DE-Brt1 DE-D161 |
imprint |
Cambridge University Press (CUP), 2019 |
imprint_str_mv |
Cambridge University Press (CUP), 2019 |
issn |
1471-0684 1475-3081 |
issn_str_mv |
1471-0684 1475-3081 |
language |
English |
mega_collection |
Cambridge University Press (CUP) (CrossRef) |
match_str |
calimeri2019optimizinganswersetcomputationviaheuristicbaseddecomposition |
publishDateSort |
2019 |
publisher |
Cambridge University Press (CUP) |
recordtype |
ai |
record_format |
ai |
series |
Theory and Practice of Logic Programming |
source_id |
49 |
title |
Optimizing Answer Set Computation via Heuristic-Based Decomposition |
title_unstemmed |
Optimizing Answer Set Computation via Heuristic-Based Decomposition |
title_full |
Optimizing Answer Set Computation via Heuristic-Based Decomposition |
title_fullStr |
Optimizing Answer Set Computation via Heuristic-Based Decomposition |
title_full_unstemmed |
Optimizing Answer Set Computation via Heuristic-Based Decomposition |
title_short |
Optimizing Answer Set Computation via Heuristic-Based Decomposition |
title_sort |
optimizing answer set computation via heuristic-based decomposition |
topic |
Artificial Intelligence Computational Theory and Mathematics Hardware and Architecture Theoretical Computer Science Software |
url |
http://dx.doi.org/10.1017/s1471068419000036 |
publishDate |
2019 |
physical |
603-628 |
description |
<jats:title>Abstract</jats:title><jats:p>Answer Set Programming (ASP) is a purely declarative formalism developed in the field of logic programming and non-monotonic reasoning: computational problems are encoded by logic programs whose answer sets, corresponding to solutions, are computed by an ASP system. Different, semantically equivalent, programs can be defined for the same problem; however, performance of systems evaluating them might significantly vary. We propose an approach for automatically transforming an input logic program into an equivalent one that can be evaluated more efficiently. One can make use of existing tree-decomposition techniques for rewriting selected rules into a set of multiple ones; the idea is to guide and adaptively apply them on the basis of proper new heuristics, to obtain a smart rewriting algorithm to be integrated into an ASP system. The method is rather general: it can be adapted to any system and implement different preference policies. Furthermore, we define a set of new heuristics tailored at optimizing grounding, one of the main phases of the ASP computation; we use them in order to implement the approach into the ASP system<jats:italic>DLV</jats:italic>, in particular into its grounding subsystem<jats:italic>ℐ-DLV</jats:italic>, and carry out an extensive experimental activity for assessing the impact of the proposal.</jats:p> |
container_issue |
4 |
container_start_page |
603 |
container_title |
Theory and Practice of Logic Programming |
container_volume |
19 |
format_de105 |
Article, E-Article |
format_de14 |
Article, E-Article |
format_de15 |
Article, E-Article |
format_de520 |
Article, E-Article |
format_de540 |
Article, E-Article |
format_dech1 |
Article, E-Article |
format_ded117 |
Article, E-Article |
format_degla1 |
E-Article |
format_del152 |
Buch |
format_del189 |
Article, E-Article |
format_dezi4 |
Article |
format_dezwi2 |
Article, E-Article |
format_finc |
Article, E-Article |
format_nrw |
Article, E-Article |
_version_ |
1792329157426806784 |
geogr_code |
not assigned |
last_indexed |
2024-03-01T13:04:43.028Z |
geogr_code_person |
not assigned |
openURL |
url_ver=Z39.88-2004&ctx_ver=Z39.88-2004&ctx_enc=info%3Aofi%2Fenc%3AUTF-8&rfr_id=info%3Asid%2Fvufind.svn.sourceforge.net%3Agenerator&rft.title=Optimizing+Answer+Set+Computation+via+Heuristic-Based+Decomposition&rft.date=2019-07-01&genre=article&issn=1475-3081&volume=19&issue=4&spage=603&epage=628&pages=603-628&jtitle=Theory+and+Practice+of+Logic+Programming&atitle=Optimizing+Answer+Set+Computation+via+Heuristic-Based+Decomposition&aulast=ZANGARI&aufirst=JESSICA&rft_id=info%3Adoi%2F10.1017%2Fs1471068419000036&rft.language%5B0%5D=eng |
SOLR | |
_version_ | 1792329157426806784 |
author | CALIMERI, FRANCESCO, PERRI, SIMONA, ZANGARI, JESSICA |
author_facet | CALIMERI, FRANCESCO, PERRI, SIMONA, ZANGARI, JESSICA, CALIMERI, FRANCESCO, PERRI, SIMONA, ZANGARI, JESSICA |
author_sort | calimeri, francesco |
container_issue | 4 |
container_start_page | 603 |
container_title | Theory and Practice of Logic Programming |
container_volume | 19 |
description | <jats:title>Abstract</jats:title><jats:p>Answer Set Programming (ASP) is a purely declarative formalism developed in the field of logic programming and non-monotonic reasoning: computational problems are encoded by logic programs whose answer sets, corresponding to solutions, are computed by an ASP system. Different, semantically equivalent, programs can be defined for the same problem; however, performance of systems evaluating them might significantly vary. We propose an approach for automatically transforming an input logic program into an equivalent one that can be evaluated more efficiently. One can make use of existing tree-decomposition techniques for rewriting selected rules into a set of multiple ones; the idea is to guide and adaptively apply them on the basis of proper new heuristics, to obtain a smart rewriting algorithm to be integrated into an ASP system. The method is rather general: it can be adapted to any system and implement different preference policies. Furthermore, we define a set of new heuristics tailored at optimizing grounding, one of the main phases of the ASP computation; we use them in order to implement the approach into the ASP system<jats:italic>DLV</jats:italic>, in particular into its grounding subsystem<jats:italic>ℐ-DLV</jats:italic>, and carry out an extensive experimental activity for assessing the impact of the proposal.</jats:p> |
doi_str_mv | 10.1017/s1471068419000036 |
facet_avail | Online |
finc_class_facet | Informatik, Mathematik, Technik |
format | ElectronicArticle |
format_de105 | Article, E-Article |
format_de14 | Article, E-Article |
format_de15 | Article, E-Article |
format_de520 | Article, E-Article |
format_de540 | Article, E-Article |
format_dech1 | Article, E-Article |
format_ded117 | Article, E-Article |
format_degla1 | E-Article |
format_del152 | Buch |
format_del189 | Article, E-Article |
format_dezi4 | Article |
format_dezwi2 | Article, E-Article |
format_finc | Article, E-Article |
format_nrw | Article, E-Article |
geogr_code | not assigned |
geogr_code_person | not assigned |
id | ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTAxNy9zMTQ3MTA2ODQxOTAwMDAzNg |
imprint | Cambridge University Press (CUP), 2019 |
imprint_str_mv | Cambridge University Press (CUP), 2019 |
institution | DE-Gla1, DE-Zi4, DE-15, DE-Rs1, DE-Pl11, DE-105, DE-14, DE-Ch1, DE-L229, DE-D275, DE-Bn3, DE-Brt1, DE-D161 |
issn | 1471-0684, 1475-3081 |
issn_str_mv | 1471-0684, 1475-3081 |
language | English |
last_indexed | 2024-03-01T13:04:43.028Z |
match_str | calimeri2019optimizinganswersetcomputationviaheuristicbaseddecomposition |
mega_collection | Cambridge University Press (CUP) (CrossRef) |
physical | 603-628 |
publishDate | 2019 |
publishDateSort | 2019 |
publisher | Cambridge University Press (CUP) |
record_format | ai |
recordtype | ai |
series | Theory and Practice of Logic Programming |
source_id | 49 |
spelling | CALIMERI, FRANCESCO PERRI, SIMONA ZANGARI, JESSICA 1471-0684 1475-3081 Cambridge University Press (CUP) Artificial Intelligence Computational Theory and Mathematics Hardware and Architecture Theoretical Computer Science Software http://dx.doi.org/10.1017/s1471068419000036 <jats:title>Abstract</jats:title><jats:p>Answer Set Programming (ASP) is a purely declarative formalism developed in the field of logic programming and non-monotonic reasoning: computational problems are encoded by logic programs whose answer sets, corresponding to solutions, are computed by an ASP system. Different, semantically equivalent, programs can be defined for the same problem; however, performance of systems evaluating them might significantly vary. We propose an approach for automatically transforming an input logic program into an equivalent one that can be evaluated more efficiently. One can make use of existing tree-decomposition techniques for rewriting selected rules into a set of multiple ones; the idea is to guide and adaptively apply them on the basis of proper new heuristics, to obtain a smart rewriting algorithm to be integrated into an ASP system. The method is rather general: it can be adapted to any system and implement different preference policies. Furthermore, we define a set of new heuristics tailored at optimizing grounding, one of the main phases of the ASP computation; we use them in order to implement the approach into the ASP system<jats:italic>DLV</jats:italic>, in particular into its grounding subsystem<jats:italic>ℐ-DLV</jats:italic>, and carry out an extensive experimental activity for assessing the impact of the proposal.</jats:p> Optimizing Answer Set Computation via Heuristic-Based Decomposition Theory and Practice of Logic Programming |
spellingShingle | CALIMERI, FRANCESCO, PERRI, SIMONA, ZANGARI, JESSICA, Theory and Practice of Logic Programming, Optimizing Answer Set Computation via Heuristic-Based Decomposition, Artificial Intelligence, Computational Theory and Mathematics, Hardware and Architecture, Theoretical Computer Science, Software |
title | Optimizing Answer Set Computation via Heuristic-Based Decomposition |
title_full | Optimizing Answer Set Computation via Heuristic-Based Decomposition |
title_fullStr | Optimizing Answer Set Computation via Heuristic-Based Decomposition |
title_full_unstemmed | Optimizing Answer Set Computation via Heuristic-Based Decomposition |
title_short | Optimizing Answer Set Computation via Heuristic-Based Decomposition |
title_sort | optimizing answer set computation via heuristic-based decomposition |
title_unstemmed | Optimizing Answer Set Computation via Heuristic-Based Decomposition |
topic | Artificial Intelligence, Computational Theory and Mathematics, Hardware and Architecture, Theoretical Computer Science, Software |
url | http://dx.doi.org/10.1017/s1471068419000036 |