We propose a sound and complete satisfiability algorithm for propositional multi-context systems. In essence, the algorithm is a distribution policy built on top of local reasoning procedures, one for each context, which can be implemented by (a diversity of) customized state-of-the-art SAT solvers. The foremost intuition that has motivated our algorithm, and the very potential strength of contextual reasoning, is that of keeping reasoning as local as possible. In doing so, we improve on earlier established complexity results by Massacci. Moreover, our approach could be applied to enhance recent proposals by Amir and Mcilraith towards a new partition-based reasoning paradigm; particularly, our formalism allows for a more expressive description of interpartition relations, and we provide an algorithm that is explicitly designed to deal with this expressiveness.

Satisfiability for Propositional Contexts / Serafini, Luciano; Roelofsen, Floris. - ELETTRONICO. - (2004).

Satisfiability for Propositional Contexts

Serafini, Luciano;
2004-01-01

Abstract

We propose a sound and complete satisfiability algorithm for propositional multi-context systems. In essence, the algorithm is a distribution policy built on top of local reasoning procedures, one for each context, which can be implemented by (a diversity of) customized state-of-the-art SAT solvers. The foremost intuition that has motivated our algorithm, and the very potential strength of contextual reasoning, is that of keeping reasoning as local as possible. In doing so, we improve on earlier established complexity results by Massacci. Moreover, our approach could be applied to enhance recent proposals by Amir and Mcilraith towards a new partition-based reasoning paradigm; particularly, our formalism allows for a more expressive description of interpartition relations, and we provide an algorithm that is explicitly designed to deal with this expressiveness.
2004
Trento, Italia
Università degli Studi di Trento. DEPARTMENT OF INFORMATION AND COMMUNICATION TECHNOLOGY
Satisfiability for Propositional Contexts / Serafini, Luciano; Roelofsen, Floris. - ELETTRONICO. - (2004).
Serafini, Luciano; Roelofsen, Floris
File in questo prodotto:
File Dimensione Formato  
026.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 432.08 kB
Formato Adobe PDF
432.08 kB Adobe PDF Visualizza/Apri

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/11572/358938
 Attenzione

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

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