{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,14]],"date-time":"2025-12-14T15:58:47Z","timestamp":1765727927193,"version":"3.40.5"},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"type":"print","value":"9781643684369"},{"type":"electronic","value":"9781643684376"}],"license":[{"start":{"date-parts":[[2023,9,28]],"date-time":"2023-09-28T00:00:00Z","timestamp":1695859200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,9,28]]},"abstract":"<jats:p>Answer Set Programming is widely applied research area for knowledge representation and for solving industrial domains. One of the challenges of this formalism focuses on the so-called grounding bottleneck, which addresses the efficient replacement of first-order variables by means of domain values. Recently, there have been several works in this direction, ranging from lazy grounding, hybrid solving, over translational approaches. Inspired by a translation from non-ground normal programs to ground disjunctive programs, we attack the grounding bottleneck from a more general angle. We provide a polynomial reduction for grounding disjunctive programs of bounded domain size by reducing to propositional epistemic logic programs (ELPs). By slightly adapting our reduction, we show new complexity results for non-ground programs that adhere to the measure treewidth. We complement these results by matching lower bounds under the exponential time hypothesis, ruling out significantly better algorithms.<\/jats:p>","DOI":"10.3233\/faia230277","type":"book-chapter","created":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T09:00:45Z","timestamp":1695978045000},"source":"Crossref","is-referenced-by-count":1,"title":["On the Structural Complexity of Grounding \u2013 Tackling the ASP Grounding Bottleneck via Epistemic Programs and Treewidth"],"prefix":"10.3233","author":[{"given":"Viktor","family":"Besin","sequence":"first","affiliation":[{"name":"TU Wien, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0131-6771","authenticated-orcid":false,"given":"Markus","family":"Hecher","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1594-8972","authenticated-orcid":false,"given":"Stefan","family":"Woltran","sequence":"additional","affiliation":[{"name":"TU Wien, Austria"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2023"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA230277","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T09:00:46Z","timestamp":1695978046000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA230277"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,28]]},"ISBN":["9781643684369","9781643684376"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia230277","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"type":"print","value":"0922-6389"},{"type":"electronic","value":"1879-8314"}],"subject":[],"published":{"date-parts":[[2023,9,28]]}}}