FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Wrapping Computer Algebra is Surprisingly Successful for Non-Linear SMT

Authors: Pascal Fontaine, Mizuhito Ogawa, Thomas Sturm, Van Khanh To and Xuan Tung Vu

Paper Information

Title:Wrapping Computer Algebra is Surprisingly Successful for Non-Linear SMT
Authors:Pascal Fontaine, Mizuhito Ogawa, Thomas Sturm, Van Khanh To and Xuan Tung Vu
Proceedings:SCSC Papers
Editors: Anna Maria Bigatti and Martin Brain
Keywords:SMT, decision procedures, non-linear arithmetic, interval propagation, quantifier elimination
Abstract:

ABSTRACT. We report on a prototypical tool for Satisfiability Modulo Theory solving for quantifier-free formulas in Non-linear Real Arithmetic or, more precisely, real closed fields, which uses a computer algebra system as the main component. This is complemented with two heuristic techniques, also stemming from computer algebra, viz.~interval constraint propagation and subtropical satisfiability. Our key idea is to make optimal use of existing knowledge and work in the symbolic computation community, reusing available methods and implementations to the most possible extent. Experimental results show that our approach is surprisingly efficient in practice.

Pages:8
Talk:Jul 11 11:00 (Session 64G: Extended Abstracts: Symbolic Computation)
Paper: