Research

Complexity of cylindrical decompositions of sub-Pfaffian sets


Reference:

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.

Abstract

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.

Details

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

Export

Actions (login required)

View Item