UC BERKELEY
EECS technical reports
TECHNICAL REPORTS


CSD-00-1113.pdf
CSD-00-1113.ps
Oskicat catalog record
Conditions of Use

Archive Home Page

Entailment with Conditional Equality Constraints (Extended Version)

Authors:
Su, Zhendong
Aiken, Alexander
Technical Report Identifier: CSD-00-1113
October 2000
CSD-00-1113.pdf
CSD-00-1113.ps

Abstract: Equality constraints (unification constraints) have widespread use in program analysis, most notably in static polymorphic type systems. Conditional equality constraints extend equality constraints with a weak form of subtyping to allow for more accurate analyses. We give a complete complexity characterization of the various entailment problems for conditional equality constraints and for a natural extension of conditional equality constraints.