An improved equivalence algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An improved equivalence algorithm

Full text

Pdf (278 KB)

Source

Communications of the ACM archive
Volume 7 , Issue 5 (May 1964) table of contents

Pages: 301 - 303

Year of Publication: 1964

ISSN:0001-0782

Authors

Benrard A. Galler	Univ. of Michigan, Ann Arbor
Michael J. Fisher	Univ. of Michigan, Ann Arbor

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 66, Citation Count: 17

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

ABSTRACT

An algorithm for assigning storage on the basis of EQUIVALENCE, DIMENSION and COMMON declarations is presented. The algorithm is based on a tree structure, and has reduced computation time by 40 percent over a previously published algorithm by identifying all equivalence classes with one scan of the EQUIVALENCE declarations. The method is applicable in any problem in which it is necessary to identify equivalence classes, given the element pairs defining the equivalence relation.

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.

Bruce W. Arden , Bernard A. Galler , Robert M. Graham, An algorithm for equivalence declarations, Communications of the ACM, v.4 n.7, p.310-314, July 1961 [doi>10.1145/366622.366626]

CITED BY 17

	Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979
	Marc J. van Kreveld , Mark H. Overmars, Union-copy structures and dynamic segment trees, Journal of the ACM (JACM), v.40 n.3, p.635-652, July 1993
	J. W. Jaromczyk , M. Kowaluk, A note on relative neighborhood graphs, Proceedings of the third annual symposium on Computational geometry, p.233-241, June 08-10, 1987, Waterloo, Ontario, Canada
	Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984
	Martin Loebl , Jaroslav Nešetřil, Linearity and unprovability of set union problem, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.360-366, May 02-04, 1988, Chicago, Illinois, United States
	C. Farshid Nourani, Abstract Implementations and Their Correctness Proofs, Journal of the ACM (JACM), v.30 n.2, p.343-359, April 1983
	Andrew Chi-chih Yao, On the average behavior of set merging algorithms (Extended Abstract), Proceedings of the eighth annual ACM symposium on Theory of computing, p.192-195, May 03-05, 1976, Hershey, Pennsylvania, United States
	Robert Endre Tarjan, Reference machines require non-linear time to maintain disjoint sets, Proceedings of the ninth annual ACM symposium on Theory of computing, p.18-29, May 04-04, 1977, Boulder, Colorado, United States
	Zvi Galil , Giuseppe F. Italiano, Data structures and algorithms for disjoint set union problems, ACM Computing Surveys (CSUR), v.23 n.3, p.319-344, Sept. 1991
	P. G. Moulton , M. E. Muller, DITRAN—a compiler emphasizing diagnostics, Communications of the ACM, v.10 n.1, p.45-52, Jan. 1967
	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975
	David Detlefs , Greg Nelson , James B. Saxe, Simplify: a theorem prover for program checking, Journal of the ACM (JACM), v.52 n.3, p.365-473, May 2005
	Pankaj K. Agarwal , Lars Arge , Ke Yi, I/O-efficient batched union-find and its applications to terrain analysis, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	A. D. Kennedy , Thomas Binoth , Thomas Rippon, Automating renormalization of quantum field theories, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	Michael D. Adams , R. Kent Dybvig, Efficient nondestructive equality checking for trees and graphs, ACM SIGPLAN Notices, v.43 n.9, September 2008
	Bjarke Hammersholt Roune, The Slice Algorithm for irreducible decomposition of monomial ideals, Journal of Symbolic Computation, v.44 n.4, p.358-381, April, 2009
	Per Bjesse, Word level bitwidth reduction for unbounded hardware model checking, Formal Methods in System Design, v.35 n.1, p.56-72, August 2009