Real quantifier elimination in practice (Q4247790)

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 1302474
Language Label Description Also known as
default for all languages
No label defined
    English
    Real quantifier elimination in practice
    scientific article; zbMATH DE number 1302474

      Statements

      0 references
      0 references
      0 references
      31 August 1999
      0 references
      quantifier elimination
      0 references
      polynomial roots
      0 references
      Gröbner basis
      0 references
      cylindrical decomposition
      0 references
      virtual substitution of test terms
      0 references
      REDLOG
      0 references
      0 references
      0 references
      0 references
      Real quantifier elimination in practice (English)
      0 references
      An interesting problem of quantifier elimination is defined in first order logic as follows: Given a formula \(\varphi\), find a quantifier-free formula \(\varphi'\) such that both \(\varphi\) and \(\varphi'\) are equivalent in the domain of real numbers. This paper surveys the following implemented real quantifier elimination methods: partial cylindrical algebraic decomposition, virtual substitution of test terms, and combination of Gröbner basis computations with multivariate root counting. The survey starts with Descartes' rule of signs and evolves into implementations in the available packages QEPCAD, QERRC, and especially REDLOG. The applications discussed are in constraint solving, optimization, scheduling, simulation, sizing, and diagnosis, control theory and stability, real implicitization, automatic theorem proving, computer aided design, computer vision, and solid modeling, collision detection and path finding. The examples used for illustration are all quadratic. None of the surveyed methods is universally superior to the others and it may take a combination of all three to solve particular problems. For the entire collection see [Zbl 0903.00035].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references