ASP Programs with Groundings of Small Treewidth

Bernhard Bliem

Forskningsoutput: Kapitel i bok/rapport/konferenshandlingKonferensbidragVetenskapligPeer review


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 connection-guarded 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.
Titel på gästpublikationFoundations of Information and Knowledge Systems : 10th International Symposium, FoIKS 2018, Budapest, Hungary, May 14–18, 2018, Proceedings
RedaktörerFlavio Ferrarotti, Stefan Woltran
Antal sidor17
UtgivningsortCham, Switzerland
FörlagSpringer International Publishing
Utgivningsdatum18 apr 2018
ISBN (tryckt)978-3-319-90049-0
ISBN (elektroniskt)978-3-319-90050-6
StatusPublicerad - 18 apr 2018
MoE-publikationstypA4 Artikel i en konferenspublikation
EvenemangTenth International Symposium on Foundations of Information and Knowledge Systems - Budapest, Ungern
Varaktighet: 14 maj 201818 maj 2018


NamnLecture Notes in Computer Science
ISSN (tryckt)0302-9743
ISSN (elektroniskt)1611-3349


  • 113 Data- och informationsvetenskap

Citera det här