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

CREATORChristopher W. Brown, United States Naval Academy
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE123 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-00963

Browse the full library · About the Tower of Babel