Uniform quantifier elimination and constraint query processing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Uniform quantifier elimination and constraint query processing

Full text

Pdf (905 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 1997 international symposium on Symbolic and algebraic computation table of contents

Kihei, Maui, Hawaii, United States

Pages: 21 - 27

Year of Publication: 1997

ISBN:0-89791-875-4

Author

Saugata Basu

Mathematical Sciences Research Institute, Berkeley, CA

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 11, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/258726.258739 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	J. BOCHNAK, M. COSTE, M.-F. RoY Gdomdtrie algdbrique rdelle. Springer-Verlag (1987).
	2	Michael Benedikt , Guozhu Dong , Leonid Libkin , Limsoon Wong, Relational expressive power of constraint query languages, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.5-16, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237667]
	3	Michael Ben-Or , Dexter Kozen , John Reif, The complexity of elementary algebra and geometry, Journal of Computer and System Sciences, v.32 n.2, p.251-264, April 1986 [doi>10.1016/0022-0000(86)90029-2]
	4	Michael Benedikt , Leonid Libkin, On the Structure of Queries in Constraint Query Languages, Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science, p.25, July 27-30, 1996
	5	Michael Benedikt , Leonid Libkin, Languages for relational databases over interpreted structures, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.87-98, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263672]
	6	Saugata Basu , Richard Pollack , Marie-Françoise Roy, On the combinatorial and algebraic complexity of quantifier elimination, Journal of the ACM (JACM), v.43 n.6, p.1002-1045, Nov. 1996 [doi>10.1145/235809.235813]
	7	P. J. COHEN Decision Procedures for Real and p.Adic Fields, Comm. of Pure and Applied Mathematics, Vol. XXII, 131-151 (1969).
	8	A. EHRENFEUCHT An application of games to the completeness problem for formalized theories, Fund. Math, 49, 1961.
	9	R. FAGtN Probabilities on finite models, Journal of Symbolic Logic, 41(1):50-58, 1976.
	10	Ronald Fagin, Finite-model theory—a personal perspective, Theoretical Computer Science, v.116 n.1, p.3-31, Aug. 2, 1993
	11	H. GAIFMAN On local and non-local properties, Proc. Herbrand Symposium Logic Colloquium, 105-35, North Holland. 1981.
	12	D. Yu. Grigor'ev, Complexity of deciding Tarski algebra, Journal of Symbolic Computation, v.5 n.1-2, p.65-108, February/April 1988 [doi>10.1016/S0747-7171(88)80006-3]
	13	Y. GUREVICrl Logic and the challenge of computer sci. ence, Current Trends in Theoretical Computer Science, 1-57, Computer Science Press, 1988.
	14	S. GRUMBACrl, J. Su Queries with Arithmetical Constraints, Proc. of Int. Conf. on Principles and Practice of Constraint Programming, 1995.
	15	Stéphane Grumbach , Jianwen Su, Finitely representable databases (extended abstract), Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.289-300, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182654]
	16	Stéphane Grumbach , Jianwen Su, Dense-order constraint databases (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.66-77, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212453]
	17	Paris C. Kanellakis , Dina Q. Goldin, Constraint Programming and Database Query Languages, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.96-120, April 19-22, 1994
	18	Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages, Selected papers of the 9th annual ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.26-52, August 1995, Nashville, Tennessee, United States
	19	Jan Paredaens , Jan Van den Bussche , Dirk Van Gucht, First-Order Queries on Finite Structures Over the Reals, Proceedings of the 10th Annual IEEE Symposium on Logic in Computer Science, p.79, June 26-29, 1995
	20	James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Par I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Journal of Symbolic Computation, v.13 n.3, p.255-299, March 1992
	21	A. TARSKI A Decision method for elementary algebra and geometry, University of California Press (1951).
	22	Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
	23	Volker Weispfenning, The complexity of linear problems in fields, Journal of Symbolic Computation, v.5 n.1-2, p.3-27, February/April 1988 [doi>10.1016/S0747-7171(88)80003-8]
	24	\r WEISPFENNING Quantifier elimination for real algebra- the quadratic case and beyond, AAECC 8(1997).

CITED BY 3

	Saugata Basu, New results on quantifier elimination over real closed fields and applications to constraint databases, Journal of the ACM (JACM), v.46 n.4, p.537-555, July 1999
	Michael Benedikt , Leonid Libkin, Relational queries over interpreted structures, Journal of the ACM (JACM), v.47 n.4, p.644-680, July 2000
	Wei Li , Shilong Ma, Limits of theory sequences over algebraically closed fields and applications, Discrete Applied Mathematics, v.136 n.1, p.23-43, 30 January 2004