Recent advances in real geometric reasoning
From MaRDI portal
Publication:3452275
DOI10.1007/978-3-319-21362-0_3zbMATH Open1434.68701arXiv1504.06484OpenAlexW2107737920WikidataQ59590569 ScholiaQ59590569MaRDI QIDQ3452275FDOQ3452275
Authors: Matthew England, James H. Davenport 
Publication date: 11 November 2015
Published in: Automated Deduction in Geometry (Search for Journal in Brave)
Abstract: In the 1930s Tarski showed that real quantifier elimination was possible, and in 1975 Collins gave a remotely practicable method, albeit with doubly-exponential complexity, which was later shown to be inherent. We discuss some of the recent major advances in Collins method: such as an alternative approach based on passing via the complexes, and advances which come closer to "solving the question asked" rather than "solving all problems to do with these polynomials".
Full work available at URL: https://arxiv.org/abs/1504.06484
Recommendations
- Computer Science Logic
- Quantifier elimination and cylindrical algebraic decomposition. Proceedings of a symposium, Linz, Austria, October 6--8, 1993
- scientific article; zbMATH DE number 953041
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- scientific article; zbMATH DE number 1302474
Symbolic computation and algebraic computation (68W30) Mechanization of proofs and logical operations (03B35) Cylindric and polyadic algebras; relation algebras (03G15)
Cites Work
- QEPCAD B
- Studies in Equisingularity II. Equisingularity in Codimension 1 (and Characteristic Zero)
- Computing cylindrical algebraic decomposition via triangular decomposition
- Title not available (Why is that?)
- Algorithms in real algebraic geometry
- Formal proofs in real algebraic geometry: from ordered fields to quantifier elimination
- Solving non-linear arithmetic
- Title not available (Why is that?)
- On the theories of triangular sets
- An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
- Title not available (Why is that?)
- Solving systems of polynomial inequalities in subexponential time
- Real quantifier elimination is doubly exponential
- Computing triangular systems and regular systems
- Title not available (Why is that?)
- Cylindrical algebraic decomposition using validated numerics
- Title not available (Why is that?)
- Complexity of deciding Tarski algebra
- Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
- An Incremental Algorithm for Computing Cylindrical Algebraic Decompositions
- Optimising problem formulation for cylindrical algebraic decomposition
- MetiTarski: past and future
- Cylindrical algebraic decompositions for boolean combinations
- Constructing a single open cell in a cylindrical algebraic decomposition
- Efficient projection orders for CAD
- Cylindrical algebraic sub-decompositions
- Deciding polynomial-exponential problems
- The complexity of quantifier elimination and cylindrical algebraic decomposition
- Truth table invariant cylindrical algebraic decomposition
- On Equimultiple Subvarieties of Algebroid Hypersurfaces
- Choosing a Variable Ordering for Truth-Table Invariant Cylindrical Algebraic Decomposition by Incremental Triangular Decomposition
- Cylindrical algebraic decomposition using local projections
- Title not available (Why is that?)
- Testing elementary function identities using CAD
- The complexity of deciding consistency of systems of polynomials in exponent inequalities
- Using the Regular Chains Library to Build Cylindrical Algebraic Decompositions by Projecting and Lifting
- Truth Table Invariant Cylindrical Algebraic Decomposition by Regular Chains
- Problem Formulation for Truth-Table Invariant Cylindrical Algebraic Decomposition by Incremental Triangular Decomposition
- Applying Machine Learning to the Problem of Choosing a Heuristic to Select the Variable Ordering for Cylindrical Algebraic Decomposition
- Quantifier elimination by cylindrical algebraic decomposition based on regular chains
- Title not available (Why is that?)
Cited In (2)
Uses Software
This page was built for publication: Recent advances in real geometric reasoning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452275)
