New results on quantifier elimination over real closed fields and applications to constraint databases

DOI10.1145/320211.320240zbMath1065.03507OpenAlexW2017027749WikidataQ129323773 ScholiaQ129323773MaRDI QIDQ3158549

Publication date: 25 January 2005

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/320211.320240

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Database theory (68P15) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Decidability of theories and sets of sentences (03B25) Quantifier elimination, model completeness, and related topics (03C10)

Related Items (21)

Symbolic Model Checking in Non-Boolean Domains ⋮ Computing uniformly optimal strategies in two-player stochastic games ⋮ Quantifier elimination for the reals with a predicate for the powers of two ⋮ Logic for physical space. From antiquity to present day ⋮ On the complexity of quantified linear systems ⋮ Fast simplifications for Tarski formulas based on monomial inequalities ⋮ Computing with Tarski formulas and semi-algebraic sets in a web browser ⋮ The past and future of embedded finite model theory ⋮ \(q\)-Bessel positive definite and \(D _{q }\)-completely monotonic functions ⋮ Limits of theory sequences over algebraically closed fields and applications. ⋮ Stochastic limit-average games are in EXPTIME ⋮ Out of order quantifier elimination for standard quantified linear programs ⋮ On metrics for probabilistic systems: definitions and algorithms ⋮ Constraint Markov chains ⋮ Generalizations of Kochen and Specker's theorem and the effectiveness of Gleason's theorem ⋮ Approximation schemes for \(r\)-weighted minimization knapsack problems ⋮ From simplification to a partial theory solver for non-linear real polynomial constraints ⋮ Geometric complexity theory V: Efficient algorithms for Noether normalization ⋮ Quantifier elimination by cylindrical algebraic decomposition based on regular chains ⋮ An incremental algorithm for DLO quantifier elimination via constraint propagation ⋮ Anderson localization for Schrödinger operators on \(\mathbb{Z}^2\)with quasi-periodic potential

This page was built for publication: New results on quantifier elimination over real closed fields and applications to constraint databases