Finding connected components of a semialgebraic set in subexponential time | Zendy

John Canny | Zendy; D. Yu. Grigor'ev | Zendy; Nicolai Vorobjov | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Finding connected components of a semialgebraic set in subexponential time

Author(s) -

John Canny,

D. Yu. Grigor'ev,

Nicolai Vorobjov

Publication year - 1992

Publication title -

applicable algebra in engineering communication and computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.558

H-Index - 35

eISSN - 1432-0622

pISSN - 0938-1279

DOI - 10.1007/bf01614146

Subject(s) - mathematics , integer (computer science) , quantifier elimination , combinatorics , set (abstract data type) , algebraic number , order (exchange) , discrete mathematics , upper and lower bounds , value (mathematics) , type (biology) , computer science , mathematical analysis , biology , ecology , statistics , finance , economics , programming language

Let a semialgebraic set be given by a quantifier-free formula of the first-order theory of real closed fields with atomic subformulae of type ( ≥ 0), 1 ≤ ≤k where the polynomials ε ℤ[,..., X] have degrees deg( < and the absolute value of each (integer) coefficient of is at most 2. An algorithm is designed which finds the connected components of the semialgebraic set in time. The best previously known bound for this problem follows from Collins' method of Cylindrical Algebraic Decomposition.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research