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.