We address the problems of combining satisfiability procedures and consider two combination scenarios: (i) the combination within the class of rewriting-based satisfiability procedures and (ii) the Nelson-Oppen combination of rewriting-based satisfiability procedures and arbitrary satisfiability procedures. In each scenario, we use meta-saturation, which schematizes saturation of the set containing the axioms of a given theory and an arbitrary set of ground literals, to syntactically decide sufficient conditions for the combinability of rewriting-based satisfiability procedures. For (i), we give a sufficient condition for the modular termination of meta-saturation. When meta-saturation for the union of theories halts, it yields a rewriting-based satisfiability procedure for the union. For (ii), we use meta-saturation to prove the stable infiniteness of the component theories and deduction completeness of their rewriting-based satisfiability procedures. These properties are important to establish the correctness of the Nelson-Oppen combination method and to obtain an efficient implementation. © Springer-Verlag Berlin Heidelberg 2006.

Automatic combinability of rewriting-based satisfiability procedures / Kirchner, H.; Ranise, S.; Ringeissen, C.; Tran, D. -K.. - 4246:(2006), pp. 542-556. (Intervento presentato al convegno 13th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2006 tenutosi a Phnom Penh, khm nel 2006) [10.1007/11916277_37].

Automatic combinability of rewriting-based satisfiability procedures

Ranise S.;
2006-01-01

Abstract

We address the problems of combining satisfiability procedures and consider two combination scenarios: (i) the combination within the class of rewriting-based satisfiability procedures and (ii) the Nelson-Oppen combination of rewriting-based satisfiability procedures and arbitrary satisfiability procedures. In each scenario, we use meta-saturation, which schematizes saturation of the set containing the axioms of a given theory and an arbitrary set of ground literals, to syntactically decide sufficient conditions for the combinability of rewriting-based satisfiability procedures. For (i), we give a sufficient condition for the modular termination of meta-saturation. When meta-saturation for the union of theories halts, it yields a rewriting-based satisfiability procedure for the union. For (ii), we use meta-saturation to prove the stable infiniteness of the component theories and deduction completeness of their rewriting-based satisfiability procedures. These properties are important to establish the correctness of the Nelson-Oppen combination method and to obtain an efficient implementation. © Springer-Verlag Berlin Heidelberg 2006.
2006
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
Springer Verlag
978-3-540-48281-9
978-3-540-48282-6
Kirchner, H.; Ranise, S.; Ringeissen, C.; Tran, D. -K.
Automatic combinability of rewriting-based satisfiability procedures / Kirchner, H.; Ranise, S.; Ringeissen, C.; Tran, D. -K.. - 4246:(2006), pp. 542-556. (Intervento presentato al convegno 13th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2006 tenutosi a Phnom Penh, khm nel 2006) [10.1007/11916277_37].
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/11572/333000
 Attenzione

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

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