Complexity of cylindrical decompositions of sub-Pfaffian sets

A Gabrielov, N Vorobjov

Research output: Contribution to journalArticlepeer-review

17 Citations (SciVal)


We construct an algorithm for a cylindrical cell decomposition of a closed cube I(n)subset ofR(n) compatible with a "restricted" sub-Pfaffian subset Y subset ofI(n), provided an oracle deciding consistency of a system of Pfaffian equations and inequalities is given. In particular, the algorithm produces the complement (Y) over tilde = I-n/Y. The complexity bound of the algorithm, the number and formats of cells are doubly exponential in n(3). (C) 2001 Elsevier Science B.V. All rights reserved.
Original languageEnglish
Pages (from-to)179-197
Number of pages19
JournalJournal of Pure and Applied Algebra
Issue number1-2
Publication statusPublished - 2001

Bibliographical note

ID number: ISI:000171099100012


Dive into the research topics of 'Complexity of cylindrical decompositions of sub-Pfaffian sets'. Together they form a unique fingerprint.

Cite this