Probabilistic Answer Set Programming is an efficient formalism to express uncertain information with an answer set program (PASP). Recently, this formalism has been extended with statistical statements, i.e., statements that can encode a certain property of the considered domain, within the PASTA framework. To perform inference, these statements are converted into answer set rules and constraints with aggregates. The complexity of PASP has been studied in depth, with results regarding both membership and completeness. However, a complexity analysis of programs with statements is missing. In this paper, we close this gap by studying the complexity of PASTA statements.

A First Journey into the Complexity of Statistical Statements in Probabilistic Answer Set Programming

Azzolini Damiano
Primo
;
2024

Abstract

Probabilistic Answer Set Programming is an efficient formalism to express uncertain information with an answer set program (PASP). Recently, this formalism has been extended with statistical statements, i.e., statements that can encode a certain property of the considered domain, within the PASTA framework. To perform inference, these statements are converted into answer set rules and constraints with aggregates. The complexity of PASP has been studied in depth, with results regarding both membership and completeness. However, a complexity analysis of programs with statements is missing. In this paper, we close this gap by studying the complexity of PASTA statements.
2024
Probabilistic Answer Set Programming, Computational Complexity, Statistical Statements
File in questo prodotto:
File Dimensione Formato  
paper2PLP24.pdf

solo gestori archivio

Descrizione: Full text editoriale
Tipologia: Full text (versione editoriale)
Licenza: Creative commons
Dimensione 956.62 kB
Formato Adobe PDF
956.62 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11392/2569773
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact