ASP Programs with Groundings of Small Treewidth

Abstract

Recent experiments have shown ASP solvers to run significantly faster on ground programs of small treewidth. If possible, it may therefore be beneficial to write a non-ground ASP encoding such that grounding it together with an input of small treewidth leads to a propositional program of small treewidth. In this work, we prove that a class of non-ground programs called guarded ASP guarantees this property. Guarded ASP is a subclass of the recently proposed class of connectionguarded ASP, which is known to admit groundings whose treewidth depends on both the treewidth and the maximum degree of the input. Here we show that this dependency on the maximum degree cannot be dropped. Hence, in contrast to connection-guarded ASP, guarded ASP promises good performance even if the input has large maximum degree.