An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs

DOI10.1016/S0022-4049(97)00068-6zbMath0929.68132MaRDI QIDQ1295548

Juan Sabia, Susana Puddu

Publication date: 16 August 1999

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

zbMATH Keywords

quantifier elimination

Mathematics Subject Classification ID

68W30: Symbolic computation and algebraic computation

03C60: Model-theoretic algebra

03C10: Quantifier elimination, model completeness, and related topics

03-04: Software, source code, etc. for problems pertaining to mathematical logic and foundations

Related Items

A new method to obtain lower bounds for polynomial evaluation, Computing bases of complete intersection rings in Noether position, Polynomial bounds for invariant functions separating orbits

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
• On computing the determinant in small parallel time using a small number of processors
• Definability and fast quantifier elimination in algebraically closed fields
• How to compute the Chow form of an unmixed polynomial ideal in single exponential time
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• Bounds for the degrees in the Nullstellensatz
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Straight-line programs in geometric elimination theory
• On the representation of rational functions of bounded complexity
• On the efficiency of effective Nullstellensätze
• Berechnung und Programm. I
• Effective Bezout identities in \({\mathbb{Q}}[z_ 1,\dots ,z_ n\)]
• THE COMPLEXITY OF THE DECISION PROBLEM FOR THE FIRST ORDER THEORY OF ALGEBRAICALLY CLOSED FIELDS
• Greatest common divisors of polynomials given by straight-line programs
• On Relating Time and Space to Size and Depth
• ESTIMATES FOR THE ORDERS OF ZEROS OF FUNCTIONS OF A CERTAIN CLASS AND APPLICATIONS IN THE THEORY OF TRANSCENDENTAL NUMBERS
• Sharp Effective Nullstellensatz
• Fast parallel matrix and GCD computations