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

Content Provider	ACM Digital Library
Author	Basu, Saugata
Copyright Year	1999
Abstract	In this paper, we give a new algorithm for quantifier elimination in the first order theory of real closed fields that improves the complexity of the best known algorithm for this problem till now. Unlike previously known algorithms [Basu et al. 1996; Renegar 1992; Heintz et al. 1990], the combinatorial part of the complexity (the part depending on the number of polynomials in the input) of this new algorithm is independent of the number of free variables. Moreover, under the assumption that each polynomial in the input depends only on a constant number of the free variables, the algebraic part of the complexity(the part depending on the degrees of the input polynomials) can also be made independent of the number of free variables. This new feature of our algorithm allow us to obtain a new algorithm for a variant of the quantifier elimination problem. We give an almost optimal algorithm for this new problem, which we call the uniform quantifier elimination problem.Using tthe uniform quantifier elimination algorithm, we give an algorithm for solving a problem arising in the field of constraint databases with real polynomial constraints. We give an algorithm for converting a query with natural domain semantics to an equivalent one with active domain semantics. A nonconstructive version of this result was proved in Benedikt et al. [1998]. Very recently, a constructive proof was also given independently in Benedikt and Libkin [1997]. However, complexity issues were not considered and no algorithm with a reasonable complexity bound was known for this latter problem till now.We also point out interesting logical consequences of this algorithmic result, concerning the expressive power of a constraint query language over the reals. This leads to simpler and constructive proofs for these inexpressibility results than the ones known before.Moreover, our improved algorithm for performing quantifier elimination immediately leads to improved algorithms for several problems for which quantifier elimination is a basic step, for example, the problem of computing the closure of a given semi-algebraic set.
Starting Page	537
Ending Page	555
Page Count	19
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/320211.320240
Journal	Journal of the ACM (JACM)
Volume Number	46
Issue Number	4
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1999-07-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the combinatorial and algebraic complexity of quantifier elimination

Relational queries over interpreted structures

New Results on Quantifier Elimination Over Real Closed Fields and Applications to Constraint Databases (1999)

Definable relations and first-order query languages over strings

Computations of Bilinear Forms over Finite Fields

Matrix sparsification and nested dissection over arbitrary fields

Multiplicative complexity of polynomial multiplication over finite fields

Disaggregations in databases

New applications of failure functions

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

Similar Documents

On the combinatorial and algebraic complexity of quantifier elimination

Relational queries over interpreted structures

New Results on Quantifier Elimination Over Real Closed Fields and Applications to Constraint Databases (1999)

Definable relations and first-order query languages over strings

Computations of Bilinear Forms over Finite Fields

Matrix sparsification and nested dissection over arbitrary fields

Multiplicative complexity of polynomial multiplication over finite fields

Disaggregations in databases

New applications of failure functions

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