|
Archive@NYU >
Stern School of Business >
IOMS: Information Systems Working Papers >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/2451/14397
|
| Title: | ORDER-SORTED RIGID E-UNIFICATION |
| Authors: | Gallier, Jean H.
Isakowitz, Tomas |
| Issue Date: | Dec-1991 |
| Publisher: | Stern School of Business, New York University |
| Series/Report no.: | IS-91-40 |
| Abstract: | Rigid E-Unification is a special type of unification which arises
naturally when extending Andrew's method of matings to logic with
equality. We study the rigid E-Unification problem in the presence of
subsorts. We present an order sorted method for the computation of order
sorted rigid-E-unifiers. The method is based on an unsorted one which we
refine and extend to handle sort information. Our approach is to
incorporate the sort information within the method so as to leverage it.
We show via examples how the order sorted method is able to detect
failures due to sort conflicts at an early stage in the construction of
potential rigid E Unifiers. The algorithm presented here is NP-complete,
as is the unsorted one. This is significant, specially due to the
complications presented by the sort information. |
| URI: | http://hdl.handle.net/2451/14397 |
| Appears in Collections: | IOMS: Information Systems Working Papers
|
All items in Faculty Digital Archive are protected by copyright, with all rights reserved.
|
