Linear unification

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear unification

Full text

Pdf (362 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighth annual ACM symposium on Theory of computing table of contents

Hershey, Pennsylvania, United States

Pages: 181 - 186

Year of Publication: 1976

Authors

M. S. Paterson
M. N. Wegman

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

ABSTRACT

A unification algorithm is described which tests a set of expressions for unifiability and which requires time and space which are only linear in the size of the input.

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	Robinson, J.A. 'Computational logic: the unification computation'. Machine Intelligence 6, 63-72.
	2	Robinson, J. A. private communication, October 1975.
	3	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 [doi>10.1145/321879.321884]

CITED BY 12

	Christoph M. Hoffmann , Michael J. O'Donnell, Pattern Matching in Trees, Journal of the ACM (JACM), v.29 n.1, p.68-95, Jan. 1982
	Gérard Huet, Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems: Abstract Properties and Applications to Term Rewriting Systems, Journal of the ACM (JACM), v.27 n.4, p.797-821, Oct. 1980
	Kevin Knight, Unification: a multidisciplinary survey, ACM Computing Surveys (CSUR), v.21 n.1, p.93-124, March 1989
	Harry R. Lewis, The equivalence problem for program schemata with nonintersecting loops, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.253-266, January 17-19, 1977, Los Angeles, California
	K. N. Venkataraman, Decidability of the purely existential fragment of the theory of term algebras, Journal of the ACM (JACM), v.34 n.2, p.492-510, April 1987
	Norihisa Suzuki, Inferring types in Smalltalk, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.187-199, January 26-28, 1981, Williamsburg, Virginia
	J. I. Glasgow , M. A. Jenkins , E. Blevis , M. P. Féret, Logic Programming with Arrays, IEEE Transactions on Knowledge and Data Engineering, v.3 n.3, p.307-319, September 1991
	Peter Downey , Hanan Samet , Ravi Sethi, Off-line and on-line algorithms for deducing equalities, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.158-170, January 23-25, 1978, Tucson, Arizona
	Manish Vachharajani , Neil Vachharajani , Sharad Malik , David I. August, Facilitating reuse in hardware models with enhanced type inference, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden
	Bernard Lang, Matching with multiplication and exponentiation (extended abstract), Mathematical Structures in Computer Science, v.15 n.5, p.959-968, October 2005
	Takahira Yamaguchi , Yoshikazu Tezuka , Osamu Kakusho, Parallel processing of resolution, Proceedings of the 9th international joint conference on Artificial intelligence, p.1178-1180, August 18-23, 1985, Los Angeles, California
	Jared L. Darlington, Improving the efficiency of higher order unification, Proceedings of the 5th international joint conference on Artificial intelligence, p.520-525, August 22-25, 1977, Cambridge, USA