Big proof engines as little proof engines: new results on decision procedures for satisfiability modulo a theory

Relatore:  Prof.ssa Maria Paola Bonacina - Dipartimento di Informatica, Universita` di Verona
  martedì 13 settembre 2005 alle ore 17.30 - caffe`, te` & C. ore 17.00
After a brief historical overview of the development of two paradigms
of automated reasoning ("big" proof engines and "little" proof engines),
this talk presents an approach to apply an inference system for first-order
logic with equality ("big" engine) as a decision procedure ("little" engine)
for satisfiability modulo a theory. Theories where satisfiability is
decidable include those of common data structures (e.g., lists, arrays,
sets and records) that are relevant for software verification.
A key step of this approach is to establish termination of the inference
system on the satisfiability problems: we present new termination results
and a general modularity theorem for termination on combinations of theories.
The combination of theories is crucial, because problems arising from
applications typically involve more than one theory.
To assess the practicality of this approach, we compared a state-of-the-art
"big engine" - the first-order theorem prover "E" - with two top-notch
"little engines" - the validity checkers CVC and CVC Lite - on both synthetic
and real-world benchmarks, including both valid and invalid instances.
Synthetic benchmarks are parametric and allow us to test how performance
scale with input size, while real-world benchmarks test the ability to handle
huge sets of literals. Contrary to the folklore that a general-purpose prover
cannot compete with specialized reasoners, the experiments are overall
favorable to the theorem prover, showing that our approach is both elegant
and practical.
Maria Paola Bonacina

Data pubblicazione
7 settembre 2005

Offerta formativa