QEPCAD B (Q4810199)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2096216
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | QEPCAD B |
scientific article; zbMATH DE number 2096216 |
Statements
QEPCAD B (English)
0 references
1 September 2004
0 references
algebraic simplification
0 references
quantifier elimination
0 references
cylindrical algebraic decomposition
0 references
0.8411154747009277
0 references
0.8397389650344849
0 references
0.8361283540725708
0 references
0.8349665999412537
0 references
0.8074521422386169
0 references
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.
0 references