QEPCAD B
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.
- Partial cylindrical algebraic decomposition for quantifier elimination
- Quantifier elimination and cylindrical algebraic decomposition. Proceedings of a symposium, Linz, Austria, October 6--8, 1993
- Simple CAD construction and its applications
- An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
- Cylindrical algebraic decomposition using local projections
- Parametric polynomial spectral factorization using the sum of roots and its application to a control design problem
- Quantifier elimination in applied mechanics problems with cylindrical algebraic decomposition
- QEPCAD
- A survey of some methods for real quantifier elimination, decision, and satisfiability and their applications
- Deciding univariate polynomial problems using untrusted certificates in Isabelle/HOL
- Global optimization of polynomials over real algebraic sets
- Automatic generation of bounds for polynomial systems with application to the Lorenz system
- On the algebraic boundaries among typical ranks for real binary forms
- Multistationarity in the space of total concentrations for systems that admit a monomial parametrization
- Using machine learning to improve cylindrical algebraic decomposition
- The impact on the properties of the EFGM copulas when extending this family
- Algorithmic reduction of biological networks with multiple time scales
- A comparison of algorithms for proving positivity of linearly recurrent sequences
- Polynomial bivariate copulas of degree five: characterization and some particular inequalities
- A local Fourier convergence analysis of a multigrid method using symbolic computation
- On quantified linear implications
- Identifying the parametric occurrence of multiple steady states for some biological networks
- Fully incremental cylindrical algebraic decomposition
- Cylindrical algebraic decomposition with equational constraints
- Special algorithm for stability analysis of multistable biological regulatory systems
- Erratum to: ``Analyzing restricted fragments of the theory of linear arithmetic
- Polynomial optimization with applications to stability analysis and control -- alternatives to sum of squares
- A hypergeometric inequality
- Real quantifier elimination for the synthesis of optimal numerical algorithms (case study: square root computation)
- An incremental algorithm for computing cylindrical algebraic decompositions
- \textsf{SC}\(^2\): satisfiability checking meets symbolic computation. (Project paper)
- On the feasibility of semi-algebraic sets in Poisson regression
- An effective implementation of a symbolic-numeric cylindrical algebraic decomposition for optimization problems
- Efficient simplification techniques for special real quantifier elimination with applications to the synthesis of optimal numerical algorithms
- Toward Computer-Assisted Discovery and Automated Proofs of Cutting Plane Theorems
- Synthesizing switching controllers for hybrid systems by generating invariants
- Heuristics for exact nonnegative matrix factorization
- Formal modelling, analysis and verification of hybrid systems
- Adapting real quantifier elimination methods for conflict set computation
- Virtual substitution for SMT-solving
- Recent advances in real geometric reasoning
- Extending a Resolution Prover for Inequalities on Elementary Functions
- An SOS-QE approach to nonlinear gain analysis for polynomial dynamical systems
- Periodically Controlled Hybrid Systems
- Combined Decision Techniques for the Existential Theory of the Reals
- An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
- On the complexity of quantified linear systems
- On invariant checking
- Dominance in the family of Sugeno-Weber t-norms
- Variant quantifier elimination
- Applications of real number theorem proving in PVS
- Cylindrical algebraic sub-decompositions
- Quantifier elimination for a class of exponential polynomial formulas
- A complexity perspective on entailment of parameterized linear constraints
- Analyzing restricted fragments of the theory of linear arithmetic
- Integrating systems around the user: combining Isabelle, Maple, and QEPCAD in the prover's palette
- A repository for CAD examples
- Real World Verification
- The (B) Conjecture for Uniform Measures in the Plane
- Hybrid Automata in Systems Biology: How Far Can We Go?
- Parametric optimization and optimal control using algebraic geometry methods
- Quantifier Elimination for Approximate Factorization of Linear Partial Differential Operators
- Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition
- MetiTarski: An Automatic Prover for the Elementary Functions
- Combining Isabelle and QEPCAD-B in the Prover’s Palette
- Truth table invariant cylindrical algebraic decomposition
- Cylindrical algebraic decomposition using local projections
- VerifyRealRoots: a Matlab package for computing verified real solutions of polynomials systems of equations and inequalities
- Accelerating parameter synthesis using semi-algebraic constraints
- Faithful real-time animation of parametrized (semi-) algebraic expressions via cylindrical algebraic decomposition
- Parametric root finding for supporting proving and discovering geometric inequalities in GeoGebra
- A systematic approach for doing an a priori identifiability study of dynamical nonlinear models
- A word reconstruction problem for polynomial regular languages
- Inner and outer approximations of arbitrarily quantified reachability problems
- Jacobi stability analysis for systems of ODEs with symbolic computation
- Optimizing a particular real root of a polynomial by a special cylindrical algebraic decomposition
- Inner and outer approximate quantifier elimination for general reachability problems
- The geometry of cylindrical algebraic decomposition
- Jacobi stability analysis for systems of ODEs using symbolic computation
- A geometric approach to cylindrical algebraic decomposition
- Extensions of the cylindrical algebraic covering method for quantifiers
- Breaking the data barrier in learning symbolic computation: a case study on variable ordering suggestion for cylindrical algebraic decomposition
- Parametric toricity of steady state varieties of reaction networks
- Automatic computation of the complete root classification for a parametric polynomial
- Exact safety verification of hybrid systems using sums-of-squares representation
- Quantifier elimination supported proofs in the numerical treatment of fluid flows
- Hybrid automata, reachability, and systems biology
- MetiTarski: An automatic theorem prover for real-valued special functions
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)