A logspace algorithm for tree canonization (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A logspace algorithm for tree canonization (extended abstract)

Full text

Pdf (543 KB)

Source

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

Victoria, British Columbia, Canada

Pages: 400 - 404

Year of Publication: 1992

ISBN:0-89791-511-9

Author

Steven Lindell

Haverford College, Haverford, PA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 28, Citation Count: 6

Additional Information:

abstract 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/129712.129750 What is a DOI?

ABSTRACT

We present a solution to the problem of assigning to each directed tree T of size n a unique isomorphism invariant name for T, using only work space O(log n). Hence, tree isomorphism is computable in logspace. As another consequence, we obtain the corollary that the set of logspace computable queries (Lspace) on trees is recursively enumerable. Our results extend easily to undirected trees and even forests.

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.

	AHU	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	Bus	S. R. Buss, The Boolean formula value problem is in ALOGTIME, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.123-131, January 1987, New York, New York, United States [doi>10.1145/28395.28409]
	D&M	Pratul Dublish , S. N. Maheshwari, Query languages with express all PTIME queries for trees and unicycle graphs, Proceedings on Mathematical foundations of computer science 1990, p.246-253, September 1990, Banska´ Bystrica, Czechoslovakia
	Fag	R. Fagin. "Generalized First-Order Spectra and Polynomial Time Recognizable Sets," in Complexity of Computation, (R. Karp, Ed.) Proc. SIAM-AMS #7 (1974), pp. 43-73.
	Imm	Neil Immerman, Languages that capture complexity classes, SIAM Journal on Computing, v.16 n.4, p.760-778, Aug. 1987 [doi>10.1137/0216051]
	M&R	Gary L. Miller , John H. Reif, Parallel tree contraction part 2: further applications, SIAM Journal on Computing, v.20 n.6, p.1128-1147, Dec. 1991 [doi>10.1137/0220070]
	Ruz	W.L. Ruzzo, "On Uniform Circuit Complexity," J. Comp. Sys. Sci., 21:2 (1981) 365-383.
	HTCSA	Handbook, of Theoretical Computer Science, Volume A, Algorithms and Complexity, edited by J. van Leeuwen, M1T Press, Elsevier, 1990.

CITED BY 6

	Kousha Etessami, Dynamic tree isomorphism via first-order updates to a relational database, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.235-243, June 01-04, 1998, Seattle, Washington, United States
	Birgit Jenner , Johannes Köbler , Pierre McKenzie , Jacobo Torán, Completeness results for graph isomorphism, Journal of Computer and System Sciences, v.66 n.3, p.549-566, May 2003
	Georg Gottlob , Christoph Koch , Reinhard Pichler , Luc Segoufin, The complexity of XPath query evaluation and XML typing, Journal of the ACM (JACM), v.52 n.2, p.284-335, March 2005
	Rémy Malgouyres , Malika More, On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology, Theoretical Computer Science, v.283 n.1, p.67-108, June 11 2002
	Luc Segoufin, Typing and querying XML documents: some complexity bounds, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.167-178, June 09-11, 2003, San Diego, California
	Jens Niehaus , Christian Igel , Wolfgang Banzhaf, Reducing the Number of Fitness Evaluations in Graph Genetic Programming Using a Canonical Graph Indexed Database, Evolutionary Computation, v.15 n.2, p.199-221, Summer 2007