Semantics of Division for Polynomial Solvers
Christopher W. Brown, United States Naval Academy · 2024
Read Semantics of Division for Polynomial Solvers by Christopher W. Brown, United States Naval Academy (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-00963.txt.
Description
Christopher Brown presents a 2024 study of a quiet problem in computer algebra: what division should mean inside logical formulas. Solvers that check such formulas, or that remove quantifiers from them, stumble on division, since a formula might divide by zero. Brown argues that the fixes used by the algebra and logic camps both fall short for such systems. He proposes a new notion, fair-satisfiability, to pin down when a formula with divisions is well formed.
Well-formed formulas are those that guard each division against a zero divisor. A translation method then turns such a formula into a pure polynomial one. The new form is satisfiable exactly when the old one is fairly satisfiable. The paper lists the good traits of this semantics and proves them. The result gives solver builders a principled way to handle division.
Catalog record
| CREATOR | Christopher W. Brown, United States Naval Academy |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 123 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-00963