Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/13254
Title: The evaluation of geometric queries: constraint databases and quantifier elimination
Authors: Heintz, Joos
Giusti, Marc
Kuijpers, Bart 
Issue Date: 2011
Abstract: We model the algorithmic task of geometric elimination (e.g., quantifier elimination in the elementary field theories of real and complex numbers) by means of certain constraint database queries, called geometric queries. As a particular case of such a geometric elimination task, we consider sample point queries. We show exponential lower complexity bounds for evaluating geometric queries in the general and in the particular case of sample point queries. Although this paper is of theoretical nature, its aim is to explore the possibilities and (complexity-)limits of computer implemented query evaluation algorithms for Constraint Databases, based on the principles of the most advanced geometric elimination procedures and their implementations, like, e.g., the software package ”Kronecker” (see [11]).
Document URI: http://hdl.handle.net/1942/13254
Link to publication: http://arxiv.org/abs/1110.2196
Category: O
Type: Preprint
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
giusti.pdf370.84 kBAdobe PDFView/Open
Show full item record

Page view(s)

10
checked on May 17, 2022

Download(s)

6
checked on May 17, 2022

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.