Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6298
Title: Determining Logical Dependency in a Decision Procedure for Equality
Authors: Krafft, Dean B.
Demers, Alan J.
Keywords: computer science
technical report
Issue Date: Apr-1981
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR81-458
Abstract: Several existing program verification and automated prooff systems make use of similar decision procedures for equality ([Krafft 1978], [Nelson and Oppen 1977] and [Downey, Sethi and Tarjan 1980]). The general method used by these algorithms has been named congruence closure. Given two expressions on uninterpreted function symbols, a congruence closure algorithm determines whether the expressions can be deduced to be equal from a set of previously asserted equalities. The existing congruence closure algorithms do not provide any indication of which previously asserted equalities were required in the deduction. In this paper, we describe an extension to one version of congruence closure. When two expressions are equal, the new algorithm can provide a certificate of their equality: a list of prevviously asserted equalities from which the queried equality can be deduced. This list is minimal, in the sense that if any equality iss removed from the list, the queried equality can no longer be deduced. The running time to produce the certificate is almost-linear in the size of the list.
URI: http://hdl.handle.net/1813/6298
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
81-458.pdf2.8 MBAdobe PDFView/Open
81-458.ps779.39 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us