Generic Computation and its complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Generic Computation and its complexity

Full text

Pdf (1.14 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 209 - 219

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Serge Abiteboul	I.N.R.I.A., Le Chesnay, France
Victor Vianu	Univ. of California at San Diego, La Jolla, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 25, Citation Count: 27

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/103418.103444 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.

	AK89	Serge Abiteboul , Paris C. Kanellakis, Object identity as a query language primitive, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.159-173, June 1989, Portland, Oregon, United States
	AV88	Abiteboul, S., V. Vianu, Datalog Extensions for Database Updates and Queries, I.N.I#.I.A. Technical Report No.715 (1988). To appear in :ICSS.
	AV89	S. Abiteboul , V. Vianu, Fixpoint extensions of first-order logic and datalog-like languages, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.71-79, June 1989, Pacific Grove, California, United States
	AV90	Serge Abiteboul , Victor Vianu, Procedural languages for database queries and updates, Journal of Computer and System Sciences, v.41 n.2, p.181-229, Oct. 1990 [doi>10.1016/0022-0000(90)90036-K]
	BR86	Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
	C81	Ashok K. Chandra, Programming primitives for database languages, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.50-62, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567537]
	C88	Ashok K. Chandra, Theory of database queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-9, March 1988, Austin, Texas, United States [doi>10.1145/308386.308396]
	CH80	Chandra, A.K., D. Harel, Computable Queries for Relational Databases, :lournM of Computer and System Sciences 21:2 (1980), 156-178.
	CH82	Chandra, A.K., D. Harel, Structure and Complexity of Relational Queries, Journal of Computer and System Sciences 25:1 (1982), 99-128.
	CH85	Chandra, A.K., D. Harel, Horn Clause Queries and Generalizations, :I. Logic Programming 2,1 (1985), pp. 1-15.
	DV91	Denninghof, K., V. Vianu, The Power of Methods With Parallel Semantics, UCSD Technical Report CS91-184 (preliminary version, 1991).
	F90	Ronald Fogin, Finite-model theory—a personal perspective, Proceedings of the third international conference on database theory on Database theory, p.3-24, November 1990, Paris, France
	G88	Gurevich, Y., Logic and the Challenge of Computer Science, Trends in Theoretical Computer Science, (E.Borger), Computer Science Press (1988). pp.l-57.
	GS85	Gurevieh Y., S. Shelah, Fixed-Point Extensions of First-Order Logic, 26th IEEE FOCS (1985), pp. 346-353.
	HS89	R. Hull , J. Su, Untyped sets, invention, and computable queries, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.347-359, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73755]
	I86	Neil Immerman, Relational queries computable in polynomial time, Information and Control, v.68 n.1-3, p.86-104, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80029-8]
	I87a	Neil Immerman, Languages that capture complexity classes, SIAM Journal on Computing, v.16 n.4, p.760-778, Aug. 1987 [doi>10.1137/0216051]
	I87b	Immerman N., Expressibility as a Complexity Measure: Results and Directions, Yale Univ. Res. Rep. DCS-TR-538, (1987).
	I89	Cai j.-W., M. Fiirer, N. Immerman, An Optimal Lower Bound on the Number of Variables for Graph Identification, Proc. IEEE FOCS (1989), pp. 612-617.
	Ko90	Kolaitis, P., Personal communication, 1990.
	K90	Paris C. Kanellakis, Elements of relational database theory, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	KP88	Phokion G. Kolaitis , Christos H. Papadimitriou, Why not negation by fixpoint?, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.231-239, March 1988, Austin, Texas, United States [doi>10.1145/308386.308446]
	KV90	Kolaitis, P., M.Y. Vardi, 0/1 Laws for Infinitary Logic, IEEE Symp. on Logic in Computer Science (1990), pp. 156-167.
	L90	Steven Lindell, An analysis of fixed-point queries on binary trees, Theoretical Computer Science, v.85 n.1, p.75-95, Aug. 5, 1991 [doi>10.1016/0304-3975(91)90048-7]
	U88	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	V82	Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]

CITED BY 27

	Allen Van Gelder, The well-founded semantics of aggregation, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.127-138, June 02-05, 1992, San Diego, California, United States
	Karl Denninghoff , Victor Vianu, Database method schemas and object creation, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.265-275, May 25-28, 1993, Washington, D.C., United States
	Phillippe Picouet , Victor Vianu, Semantics and expressiveness issues in active databases (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.126-138, May 22-25, 1995, San Jose, California, United States
	Serge Abiteboul , Kevin Compton , Victor Vianu, Queries are easier than you thought (probably), Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.23-32, June 02-05, 1992, San Diego, California, United States
	Andreas Blass , Yuri Gurevich , Jan Van den Bussche, Abstract state machines and computationally complete query languages, Information and Computation, v.174 n.1, p.20-36, April 10, 2002
	Tirza Hirst , David Harel, Completeness results for recursive data bases, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.244-252, May 25-28, 1993, Washington, D.C., United States
	Dan Suciu , Val Breazu-Tannen, A query language for NC, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.167-178, May 24-27, 1994, Minneapolis, Minnesota, United States
	Gerd G. Hillebrand , Paris C. Kanellakis, Functional database query languages as typed lambda calculi of fixed order (extended abstract), Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.222-231, May 24-27, 1994, Minneapolis, Minnesota, United States
	Piero Fraternali , Letizia Tanca, A structured approach for the definition of the semantics of active databases, ACM Transactions on Database Systems (TODS), v.20 n.4, p.414-471, Dec. 1995
	Dan Suciu , Jan Paredaens, Any algorithm in the complex object algebra with powerset needs exponential space to compute transitive closure, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.201-209, May 24-27, 1994, Minneapolis, Minnesota, United States
	Jan Van den Bussche , Dirk Van Gucht, Semi-determinism (extended abstract), Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.191-201, June 02-05, 1992, San Diego, California, United States
	Serge Abiteboul , Moshe Y. Vardi , Victor Vianu, Fixpoint logics, relational machines, and computational complexity, Journal of the ACM (JACM), v.44 n.1, p.30-56, Jan. 1997
	Latha S. Colby , Edward L. Robertson , Lawrence V. Saxton , Dirk Van Gucht, A query language for list-based complex objects, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.179-189, May 24-27, 1994, Minneapolis, Minnesota, United States
	Alberto O. Mendelzon , Tova Milo, Formal models of Web queries, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.134-143, May 11-15, 1997, Tucson, Arizona, United States
	David Harel, Will I be pretty, will I be rich?: some thoughts on theory vs. practice in systems engineering, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-3, May 24-27, 1994, Minneapolis, Minnesota, United States
	Flavio A. Ferrarotti , José M. Turull-Torres, On the computation of approximations of database queries, Proceedings of the fifteenth Australasian database conference, p.27-37, January 01, 2004, Dunedin, New Zealand
	Lane A. Hemaspaandra, SIGACT news complexity theory column 49, ACM SIGACT News, v.36 n.4, December 2005
	Martin Grohe, Large finite structures with few L^k-types, Information and Computation, v.179 n.2, p.250-278, December 15, 2002
	Iain A. Stewart, Program schemes, arrays, Lindström quantifiers and zero-one laws, Theoretical Computer Science, v.275 n.1-2, p.283-310, March 28 2002
	Jerzy Tyszkiewicz, Computability by Sequences of Queries, Fundamenta Informaticae, v.48 n.4, p.389-414, December 2001
	Stéphane Grumbach , Zoé Lacroix, On non-determinism in machines and languages, Annals of Mathematics and Artificial Intelligence, v.19 n.1-2, p.169-213, 1997
	Victor Vianu, Rule-based languages, Annals of Mathematics and Artificial Intelligence, v.19 n.1-2, p.215-259, 1997
	Karl Denninghoff , Victor Vianu, The Power of Methods With Parallel Semantics, Proceedings of the 17th International Conference on Very Large Data Bases, p.221-232, September 03-06, 1991
	Mihalis Yannakakis, Perspectives on database theory, ACM SIGACT News, v.27 n.3, p.25-49, Sept. 1996
	Stéphane Grumbach , Leonid Libkin , Tova Milo , Limsoon Wong, Query languages for bags: expressive power and complexity, ACM SIGACT News, v.27 n.2, p.30-44, June 1996
	David Harel, Will I be pretty, will I be rich?: some thoughts on theory vs. practice in systems engineering, ACM SIGACT News, v.26 n.2, p.21-25, June 1995
	Iain A. Stewart, Program Schemes, Queues, the Recursive Spectrum and Zero-one Laws, Fundamenta Informaticae, v.91 n.2, p.411-435, April 2009