A specialized ATMS for equivalence relations Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/6h440w53m

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • A specialized ATMS for efficiently computing equivalence relations in multiple contexts is introduced. This specialized ATMS overcomes the problems with existing solutions to reasoning with equivalence relations. The most direct implementation of an equivalence relation in the ATMS-encoding the reflexive, transitive, and symmetric rules in the consumer architecture-produces redundant equality derivations and requires Θ(n³) label update attempts (where n is the number of terms in the equivalence class). An alternative implementation is one that employs simple equivalence classes. However, this solution is unacceptable, since the number of classes grows exponentially with the number of distinct assumptions. The specialized ATMS presented here produces no redundant equality derivations, requires only Θ(n²) label update attempts, and is most efficient when there are many distinct assumptions and few nogoods. This is achieved by exploiting a special relationship that holds among the labels of the equality assertions because of transitivity. The standard dependency structure construction and traversal is replaced by a single pass over each label in a particular kind of equivalence class. The specialized ATMS has been implemented as part of the logic programming language FORLOG.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0.82 on a Canon DR-9080C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-07-15T17:29:29Z (GMT) No. of bitstreams: 1 KoffCarolineN1989.pdf: 496678 bytes, checksum: 9b1773038e9e740ec5b6c642e98f84e5 (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-05-24T17:27:53Z (GMT) No. of bitstreams: 1 KoffCarolineN1989.pdf: 496678 bytes, checksum: 9b1773038e9e740ec5b6c642e98f84e5 (MD5)
  • description.provenance : Submitted by Kim Stowell (ksscannerosu@gmail.com) on 2013-05-22T21:16:04Z No. of bitstreams: 1 KoffCarolineN1989.pdf: 496678 bytes, checksum: 9b1773038e9e740ec5b6c642e98f84e5 (MD5)
  • description.provenance : Made available in DSpace on 2013-07-15T17:29:29Z (GMT). No. of bitstreams: 1 KoffCarolineN1989.pdf: 496678 bytes, checksum: 9b1773038e9e740ec5b6c642e98f84e5 (MD5) Previous issue date: 1988-05-12

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items