Complexity of cylindrical decompositions of sub-Pfaffian sets


Gabrielov, A. and Vorobjov, N., 2001. Complexity of cylindrical decompositions of sub-Pfaffian sets. Journal of Pure and Applied Algebra, 164 (1-2), pp. 179-197.

Related documents:

This repository does not currently have the full-text of this item.
You may be able to access a copy if URLs are provided below.


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.


Item Type Articles
CreatorsGabrielov, A.and Vorobjov, N.
DepartmentsFaculty of Science > Computer Science
ID Code5626
Additional InformationID number: ISI:000171099100012


Actions (login required)

View Item