|
JAIST Repository >
School of Information Science >
JAIST Research Reports >
Research Report - School of Information Science ： ISSN 0918-7553 >
IS-RR-2013 >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10119/11349
|
| Title: | raSAT: SMT for Polynomial Inequality |
| Authors: | To, Van Khanh
Ogawa, Mizuhito |
| Keywords: | interval arithmetic
affine arithmetic
SMT
polynomial constraints
testing |
| Issue Date: | 2013-05-27 |
| Publisher: | 北陸先端科学技術大学院大学情報科学研究科 |
| Magazine name: | Research report (School of Information Science, Japan Advanced Institute of Science and Technology) |
| Volume: | IS-RR-2013-003 |
| Start page: | 1 |
| End page: | 23 |
| Abstract: | This paper presents an iterative approximation refinement, called raSAT loop, which solves polynomial inequality constraints on real numbers. The approximation scheme consists of interval arithmetic (over-approximation, aiming to decide unsatisfiability) and testing (underapproximation, aiming to decide satisfiability). If both of them fail to decide, input intervals are refined by decomposition. raSAT loop is implemented as an SMT raSAT with miniSAT 2.2 as a backend SAT solver. Experiments including simple benchmarks for estimating effects of input measures (i.e., degrees, number of variables, and number of constraints) and QF_NRA benchmarks from SMT-LIB show that raSAT is comparable to Z3 4.3, and sometimes outperforms, especially with high degree of polynomials. |
| URI: | http://hdl.handle.net/10119/11349 |
| Material Type: | publisher |
| Appears in Collections: | IS-RR-2013
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| IS-RR-2013-003.pdf | | 598Kb | Adobe PDF | View/Open |
|
All items in DSpace are protected by copyright, with all rights reserved.
|
