QEPCAD B

From MaRDI portal





Cylindrical Algebraic Decomposition (CAD) is a method for quantifier elimination developed by \textit{George Collins} [``Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition, Lect. Notes Comput. Sci. 33, 134--183 (1975; Zbl 0318.02051)]. \textit{Qepcad~b} is a development of the \textit{Qepcad} [\textit{G. E. Collins} and \textit{H. Hong}, ``Partial cylindrical algebraic decomposition for quantifier elimination, J. Symb. Comput. 12, No. 3, 299--328 (1991; Zbl 0754.68063)] implementation by Hoon Hong and is available at \url{http://www.cs.usna.edu/~qepcad}. It is a command-line program written mainly in C and based on the \textit{Saclib} library of computer algebra functions. Quantifiers (\(\exists, \forall\)) are eliminated by constructing a CAD representing a semi-algebraic set, applying the projection implied by the quantifiers to give a new CAD, and then reconstructing a formula representation. CADs can also be used for other purposes, which is one of the goals of \textit{Qepcad~b}. \textit{Qepcad~b} uses the projections due to McCallum [\textit{C. W. Brown}, ``Improved projection for cylindrical algebraic decomposition, J. Symb. Comput. 32, No. 5, 447--465 (2001; Zbl 0981.68186); \textit{S. McCallum}, ``An improved projection operator for cylindrical algebraic decomposition, in: Quantifier elimination and cylindrical algebraic decomposition, 242--268 (1998; Zbl 0906.03033)] if possible and it uses interval arithmetic [\textit{G. E. Collins, J. R. Johnson} and \textit{W. Krandick}, ``Interval arithmetic in cylindrical algebraic decomposition, J. Symb. Comput. 34, No. 2, 145--157 (2002; Zbl 1007.68210)] in the lifting phase. It always produces a formula (provided McCallum's projection succeeds). Given a quantifier-free input formula, \textit{Qepcad~b} attempts to produce a ``simpler equivalent (in some sense), which can be subject to specified assumptions. A very large formula can be simplified recursively by a program called SLFQ that applies \textit{Qepcad~b}. \textit{Qepcad~b} can produce topologically correct plots of 2-dimensional CADs (as EPS files). Constructing CADs from Tarski formulas is inefficient and \textit{Qepcad~b} allows more direct input via an extension of Tarski formulas involving equality and inequality symbols applied to roots of polynomials. \textit{Qepcad~b} allows additional quantifiers such as ``exist exactly \(k\), ``exist infinitely many and ``for all but finitely many, which aid efficiency by avoiding the need to introduce extra variables or perform unnecessary tests.




Cited in
(83)


Describes a project that uses

Uses Software






This page was built for publication: QEPCAD B

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4810199)