Dynamic tree isomorphism via first-order updates to a relational database

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dynamic tree isomorphism via first-order updates to a relational database

Full text

Pdf (1.15 MB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems table of contents

Seattle, Washington, United States

Pages: 235 - 243

Year of Publication: 1998

ISBN:0-89791-996-3

Author

Kousha Etessami

Bell Labs, 600 Mountain Ave., Murray Hill, NJ

Sponsors

SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 22, 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/275487.275514 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.

	Ajt83	M. Ajtai. ~1-formulae on finite structures. Ann. Pure and Appl. Logic, 24:1-48, 1983.
	BIS90	David A. Mix-Barrington , Neil Immerman , Howard Straubing, On uniformity within NC1, Journal of Computer and System Sciences, v.41 n.3, p.274-306, Dec. 1990 [doi>10.1016/0022-0000(90)90022-D]
	BLT86	Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
	Cai90	J. Cai, Lower bounds for constant-depth circuits in the presence of help bits, Information Processing Letters, v.36 n.2, p.79-83, Oct. 1990 [doi>10.1016/0020-0190(90)90101-3]
	CFI92	J. Cai, M. Fiirer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinator- /ca, 12 (4):389-410, 1992.
	CN96	Siu-Wing Cheng , Moon-Pun Ng, Isomorphism testing and display of symmetries in dynamic trees, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.202-211, January 28-30, 1996, Atlanta, Georgia, United States
	DS93	Guozhu Dong , Jianwen Su, First-Order Incremental Evaluation of Datalog Queries, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.295-308, August 30-September 01, 1993
	DS95	Guozhu Dong , Jianwen Su, Incremental and decremental evaluation of transitive closure by first-order queries, Information and Computation, v.120 n.1, p.101-106, July 1995 [doi>10.1006/inco.1995.1102]
	DS97a	Guozhu Dong , Jianwen Su, Arity bounds in first-order incremental evaluation and definition of polynomial time database queries, Journal of Computer and System Sciences, v.57 n.3, p.289-308, Dec. 1998 [doi>10.1006/jcss.1998.1565]
	DS97b	Guozhu Dong , Jianwen Su, Deterministic FOIES are strictly weaker, Annals of Mathematics and Artificial Intelligence, v.19 n.1-2, p.127-146, 1997 [doi>10.1023/A:1018951521198]
	EI95	Kousha Etessami , Neil Immerman, Tree Canonization and Transtive Closure, Proceedings of the 10th Annual IEEE Symposium on Logic in Computer Science, p.331, June 26-29, 1995
	Ete95	K. Etessami, Counting quantifiers, successor relations, and logarithmic space, Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), p.2, June 19-22, 1995
	GL95	Timothy Griffin , Leonid Libkin, Incremental maintenance of views with duplicates, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.328-339, May 22-25, 1995, San Jose, California, United States
	GM95	A. Gupta and I. Mumick. Maintenance of materialized views: problems, techniques, and applications. IEEE Data Engineering Bulletin, 18(2):3-19, 1995.
	GMS93	Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
	IL90	N. Immerman and E. Lander. Describing graphs: A first-order approach to graph canonization. In Alan Selman, editor, Complexity Theory Retrospective, pages 59-81. Springer-Verlag, 1990.
	Imm89a	N. Immerman. Descriptive and computational complexity. In J. Hartmanis, editor, Computational Complexity Theory, volume 38, pages 75-91. Proc. Syrup. in Applied Math., American Mathematical Society, 1989.
	Imm89b	Neil Immerman, Expressibility and parallel complexity, SIAM Journal on Computing, v.18 n.3, p.625-638, June 1989 [doi>10.1137/0218043]
	Imm98	N, Immerman. Descriptive Complexity. Springer-Verlag, 1998. to appear.
	KMW96	Sanjeev Khanna , Rajeev Motwani , Randall H. Wilson, On certificates and lookahead in dynamic graph problems, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.222-231, January 28-30, 1996, Atlanta, Georgia, United States
	Lin92	Steven Lindell, A logspace algorithm for tree canonization (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.400-404, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129750]
	LW97	Leonid Libkin , Limsoon Wong, Incremental Recomputation of Recursive Queries with Nested Sets and Aggregate Functions, Proceedings of the 6th International Workshop on Database Programming Languages, p.222-238, August 18-20, 1997
	Mil97	P. Miltersen. personal communication, 1997.
	MSVT94	Peter Bro Miltersen , Sairam Subramanian , Jeffrey Scott Vitter , Roberto Tamassia, Complexity models for incremental computation, Theoretical Computer Science, v.130 n.1, p.203-236, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90159-7]
	PI97	Sushant Patnaik , Neil Immerman, Dyn-FO: a parallel, dynamic complexity class, Journal of Computer and System Sciences, v.55 n.2, p.199-209, Oct. 1997 [doi>10.1006/jcss.1997.1520]
	QW91	X. Qian , G. Wiederhold, Incremental Recomputation of Active Relational Expressions, IEEE Transactions on Knowledge and Data Engineering, v.3 n.3, p.337-341, September 1991 [doi>10.1109/69.91063]
	Via97	V. Vianu. Databases and finite model theory. In N. Immerman and P. Kolaitis, editors, Descriptive Complexity Theory, volume 31 of DIMA CS series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1997.

CITED BY 3

	William Hesse, The dynamic complexity of transitive closure is in DynTC⁰, Theoretical Computer Science, v.296 n.3, p.473-485, 14 March 2003
	Guozhu Dong , Leonid Libkin , Limsoon Wong, Incremental recomputation in local languages, Information and Computation, v.181 n.2, p.88-98, March 15, 2003
	Chaoyi Pang , David Hansen , Anthony Maeder, Managing RBAC states with transitive relations, Proceedings of the 2nd ACM symposium on Information, computer and communications security, March 20-22, 2007, Singapore