[Back]


Talks and Poster Presentations (with Proceedings-Entry):

B. Bliem, M. Moldovan, M. Morak, S. Woltran:
"The Impact of Treewidth on ASP Grounding and Solving";
Talk: 26th International Joint Conference on Artificial Intelligence (IJCAI 2017), Melbourne, Australia; 2017-08-19 - 2017-08-25; in: "Proc. of the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017)", AAAI Press, (2017), 852 - 858.



English abstract:
In this paper, we aim to study how the performance of modern answer set programming (ASP) solvers is influenced by the treewidth of the input program and to investigate the consequences of this relationship. We first perform an experimental evaluation that shows that the solving performance is heavily influenced by the treewidth, given ground input programs that are otherwise uniform, both in size and construction. This observation leads to an important question for ASP, namely, how to design encodings such that the treewidth of the resulting ground program remains small. To this end, we define the class of connection-guarded programs, which guarantees that the treewidth of the program after grounding only depends on the treewidth (and the degree) of the input instance. In order to obtain this result, we formalize the grounding process using MSO transductions.

Keywords:
Impact;Treewidth;ASP;Grounding;Solving;


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.24963/ijcai.2017/118



Related Projects:
Project Head Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen

Project Head Stefan Woltran:
START


Created from the Publication Database of the Vienna University of Technology.