Disjunctive Logic Programming (DLP) is an advanced formalism for Knowledge Representation and Reasoning (KRR). DLP is very expressive in a precise mathematical sense: it allows to express every property of finite structures that is decidable in the complexity class (∑)p 2(NPNP). Importantly, the DLP encodings are often simple and natural. In this paper, we single out some limitations of DLP for KRR, which cannot naturally express problems where the size of the disjunction is not known "a priori" (like N-Coloring), but it is part of the input. To overcome these limitations, we further enhance the knowledge modelling abilities of DLP, by extending this language by Parametric Connectives (OR and AND). These connectives allow us to represent compactly the disjunction/conjunction of a set of atoms having a given property. We formally define the semantics of the new language, named DLPνΛand we show the usefulness of the new constructs on relevant knowledge-based problems. We analyze the computational complexity of DLP νΛshowing that the addition of parametric connectives does not bring a higher cost in that respect.

Parametric Connectives in Disjunctive Logic Programming

LEONE, Nicola;PERRI, Simona
2003

Abstract

Disjunctive Logic Programming (DLP) is an advanced formalism for Knowledge Representation and Reasoning (KRR). DLP is very expressive in a precise mathematical sense: it allows to express every property of finite structures that is decidable in the complexity class (∑)p 2(NPNP). Importantly, the DLP encodings are often simple and natural. In this paper, we single out some limitations of DLP for KRR, which cannot naturally express problems where the size of the disjunction is not known "a priori" (like N-Coloring), but it is part of the input. To overcome these limitations, we further enhance the knowledge modelling abilities of DLP, by extending this language by Parametric Connectives (OR and AND). These connectives allow us to represent compactly the disjunction/conjunction of a set of atoms having a given property. We formally define the semantics of the new language, named DLPνΛand we show the usefulness of the new constructs on relevant knowledge-based problems. We analyze the computational complexity of DLP νΛshowing that the addition of parametric connectives does not bring a higher cost in that respect.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS 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/20.500.11770/167915
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact