Efficiency of Equivalence Algorithms
This paper was first presented at the Symposium on Complexity of Computer Computations, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, on March 22, 1972. The equivalence problem is to determine the finest partition on a set that is consistent with a sequence of assertions of the...
| Main Author: | |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Online Access: | http://hdl.handle.net/1721.1/6201 |
| _version_ | 1826210806589554688 |
|---|---|
| author | Fischer, Michael J. |
| author_facet | Fischer, Michael J. |
| author_sort | Fischer, Michael J. |
| collection | MIT |
| description | This paper was first presented at the Symposium on Complexity of Computer Computations, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, on March 22, 1972. The equivalence problem is to determine the finest partition on a set that is consistent with a sequence of assertions of the form "x == y". A strategy for doing this on a computer processes the assertions serially, maintaining always in storage a representation of the partition defined by the assertions so far encountered. To process the command "x == y", the equivalence classes of x and y are determined. If they are the same, nothing further is done; otherwise the two classes are merged together. Galler and Fischer (1964A) give an algorithm for solving this problem based on tree structures, and it also appears in Knuth (1968A). The items in each equivalent class are arranged in a tree, and each item except for the root contains a pointer to its father. The root contains a flag indicating that it is a root, and it may also contain other information relevant to the equivalence class as a whole. |
| first_indexed | 2024-09-23T14:56:03Z |
| id | mit-1721.1/6201 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:56:03Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/62012019-04-12T08:29:29Z Efficiency of Equivalence Algorithms Fischer, Michael J. This paper was first presented at the Symposium on Complexity of Computer Computations, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, on March 22, 1972. The equivalence problem is to determine the finest partition on a set that is consistent with a sequence of assertions of the form "x == y". A strategy for doing this on a computer processes the assertions serially, maintaining always in storage a representation of the partition defined by the assertions so far encountered. To process the command "x == y", the equivalence classes of x and y are determined. If they are the same, nothing further is done; otherwise the two classes are merged together. Galler and Fischer (1964A) give an algorithm for solving this problem based on tree structures, and it also appears in Knuth (1968A). The items in each equivalent class are arranged in a tree, and each item except for the root contains a pointer to its father. The root contains a flag indicating that it is a root, and it may also contain other information relevant to the equivalence class as a whole. 2004-10-04T14:45:39Z 2004-10-04T14:45:39Z 1972-04-01 AIM-256 http://hdl.handle.net/1721.1/6201 en_US AIM-256 6369054 bytes 477573 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Fischer, Michael J. Efficiency of Equivalence Algorithms |
| title | Efficiency of Equivalence Algorithms |
| title_full | Efficiency of Equivalence Algorithms |
| title_fullStr | Efficiency of Equivalence Algorithms |
| title_full_unstemmed | Efficiency of Equivalence Algorithms |
| title_short | Efficiency of Equivalence Algorithms |
| title_sort | efficiency of equivalence algorithms |
| url | http://hdl.handle.net/1721.1/6201 |
| work_keys_str_mv | AT fischermichaelj efficiencyofequivalencealgorithms |