Metraipolis › archive › dc_d10092014197

Optimal Probabilistic Answer Set Programming: Complexity and Implementations — arXiv:2611.09022

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.09022
License (as archived)
CC0-1.0
Archived
2026-11-09T22:34:45.222Z
SHA-256 of the archived text
02668aa8002623dc93a0053f956a7ad3e649f9ac0cf087c2d4e3a435fe7ed822
Stable URL of this page
https://metraipolis.com/documento/dc_d10092014197

How to cite

Optimal Probabilistic Answer Set Programming: Complexity and Implementations — arXiv:2611.09022 — arXiv (en), https://arxiv.org/abs/2611.09022 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d10092014197 (Metraipolis archive dc_d10092014197, sha256 02668aa8002623dc93a0053f956a7ad3e649f9ac0cf087c2d4e3a435fe7ed822)
BibTeX
@misc{dcd10092014197,
  title = {Optimal Probabilistic Answer Set Programming: Complexity and Implementations — arXiv:2611.09022},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.09022},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d10092014197; sha256 02668aa8002623dc93a0053f956a7ad3e649f9ac0cf087c2d4e3a435fe7ed822},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.09022. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Probabilistic Answer Set Programming (PASP) extends Answer Set Programming with the possibility of representing uncertain data. Among the possible available semantics, we focus here on the credal semantics. In this setting, prior work has focused exclusively on plain ASP programs, i.e., programs without optimization constructs. However, many real world tasks define optimality criteria over the possible solutions, which cannot be conveniently modeled with existing probabilistic ASP frameworks. In this paper, we close this gap and propose optimal Probabilistic Answer Set Programming, which extends PASP by also allowing weak constraints, which are the standard optimization construct of ASP. We define the semantics of such programs, study the computational complexity of the inference and most probable explanation tasks, and propose practical implementations based on Algebraic Model Counting and Answer Set Programming with Quantifiers. An empirical evaluation of the proposed approach on three real world tasks confirms the applicability of our framework.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Logic in Computer Science (cs.LO) ; Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2611.09022 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-09T22:30:47.314Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).