Complexity of cylindrical decompositions of sub-Pfaffian sets

A Gabrielov; N Vorobjov

doi:10.1016/S0022-4049(00)00149-3

Complexity of cylindrical decompositions of sub-Pfaffian sets

A Gabrielov
, N Vorobjov

Research output: Contribution to journal › Article › peer-review

18 Citations (SciVal)

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.

Original language	English
Pages (from-to)	179-197
Number of pages	19
Journal	Journal of Pure and Applied Algebra
Volume	164
Issue number	1-2
DOIs	https://doi.org/10.1016/S0022-4049(00)00149-3
Publication status	Published - 2001

Bibliographical note

ID number: ISI:000171099100012

Access to Document

10.1016/S0022-4049(00)00149-3

Cite this

@article{fc036d57a47b4ac2ab2fe1355de1de91,

title = "Complexity of cylindrical decompositions of sub-Pfaffian sets",

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.",

author = "A Gabrielov and N Vorobjov",

note = "ID number: ISI:000171099100012",

year = "2001",

doi = "10.1016/S0022-4049(00)00149-3",

language = "English",

volume = "164",

pages = "179--197",

journal = "Journal of Pure and Applied Algebra",

issn = "0022-4049",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - Complexity of cylindrical decompositions of sub-Pfaffian sets

AU - Gabrielov, A

AU - Vorobjov, N

N1 - ID number: ISI:000171099100012

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

U2 - 10.1016/S0022-4049(00)00149-3

DO - 10.1016/S0022-4049(00)00149-3

M3 - Article

SN - 0022-4049

VL - 164

SP - 179

EP - 197

JO - Journal of Pure and Applied Algebra

JF - Journal of Pure and Applied Algebra

IS - 1-2

ER -

Complexity of cylindrical decompositions of sub-Pfaffian sets

Abstract

Bibliographical note

Access to Document

Fingerprint

Cite this