Complexity of cylindrical decompositions of sub-Pfaffian

DOI10.1016/S0022-4049(00)00149-3MaRDI QIDQ5951564zbMATH OpenOpenAlexFDO

Authors Andrei Gabrielov, Nicolai Vorobjov

Publication date 10 October 2002

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0022-4049(00)00149-3

zbMATH Keywords

algorithmcylindrical cell decompositionssub-Pfaffian sets

Mathematics Subject Classification ID

Model theory of ordered structures; o-minimality (03C64) Semi-analytic sets, subanalytic sets, and generalizations (32B20) Symbolic computation and algebraic computation (68W30)

Review text

The authors give an algorithm for obtaining cylindrical cell decompositions of sub-Pfaffian sets whose complexity bound is doubly exponential in \(n^3\), \(n\) being the dimension of the ambient affine space.

Recommendations

• scientific article; zbMATH DE number 2209738
• New complexity bounds for cylindrical decompositions of sub-Pfaffian sets
• Effective cylindrical cell decompositions for restricted sub-Pfaffian sets
• The complexity of quantifier elimination and cylindrical algebraic decomposition
• Complexity of stratifications of semi-Pfaffian sets

Cites work

• p-adic and real subanalytic sets
• Betti numbers of semi-Pfaffian sets
• Complements of subanalytic sets and existential formulas for analytic functions
• Complexity of stratifications of semi-Pfaffian sets
• Frontier and closure of a semi-Pfaffian set
• Geometric and differential properties of subanalytic sets
• scientific article; zbMATH DE number 3908819 (Why is no real title available?)
• scientific article; zbMATH DE number 49991 (Why is no real title available?)
• scientific article; zbMATH DE number 3497890 (Why is no real title available?)
• scientific article; zbMATH DE number 3564960 (Why is no real title available?)
• scientific article; zbMATH DE number 1096865 (Why is no real title available?)
• scientific article; zbMATH DE number 1160037 (Why is no real title available?)
• On the combinatorial and algebraic complexity of quantifier elimination
• On the Covering of Analytic Loci by Complexes
• Projections of semi-analytic sets
• Solving systems of polynomial inequalities in subexponential time
• The complexity of deciding consistency of systems of polynomials in exponent inequalities
• The elementary theory of restricted analytic fields with exponentiation

Cited in

(12)

• Computing combinatorial types of trajectories in Pfaffian dynamics
• Complexity of stratifications of semi-Pfaffian sets
• An unfeasibility view of neural network learning
• New complexity bounds for cylindrical decompositions of sub-Pfaffian sets
• scientific article; zbMATH DE number 2209727 (Why is no real title available?)
• scientific article; zbMATH DE number 2209738 (Why is no real title available?)
• Effective cylindrical cell decompositions for restricted sub-Pfaffian sets
• Zero counting for a class of univariate Pfaffian functions
• Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\)
• Complexity in tame quantum theories
• Multiplicities of Noetherian deformations
• Uniformization in superstructures over some extensions of \(\mathbb{R}\)

This page was built for publication: Complexity of cylindrical decompositions of sub-Pfaffian

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5951564)