Tech Talk: Ground Interpolation for Combined Theories

December 30th, 2009 by Lee Pike

The next Galois Tech Talk will be delivered by Amit Goel.  Come kick off 2010 with us!

Title: Ground Interpolation for Combined Theories

Abstract: We give a method for modular generation of ground interpolants in modern SMT solvers supporting multiple theories. Our method uses a novel algorithm to modify the proof tree obtained from an unsatifiability run of the solver into a proof tree without occurrences of troublesome “uncolorable” literals. An interpolant can then be readily generated using existing procedures. The principal advantage of our method is that it places few restrictions (none for convex theories) on the search strategy of the solver. Consequently, it is straightforward to implement and enables more efficient interpolating SMT solvers. In the presence of non-convex theories our method is incomplete, but still more general than previous methods.

• Date: Tuesday, 10:30am, 05 Jan 2010
• Time: 10:30am – 11:30am
• Location: Galois, Inc.
  421 SW 6th Ave. Suite 300
  (3rd floor of the Commonwealth Building)
  Portland, OR 97204

Bio: Amit Goel is a member of Intel’s Strategic CAD Labs.

---

Galois has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities. The talks are open and free. An RSVP is not required, but feel free to contact the organizer with questions and comments.

Leave a Reply

Name

Email address (will not be published)

Website (optional)

Comments