Entailment with Conditional Equality Constraints (Extended Version)

Zhendong Su and Alexander Aiken

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-00-1113
October 2000

http://www.eecs.berkeley.edu/Pubs/TechRpts/2000/CSD-00-1113.pdf

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.


BibTeX citation:

@techreport{Su:CSD-00-1113,
    Author = {Su, Zhendong and Aiken, Alexander},
    Title = {Entailment with Conditional Equality Constraints (Extended Version)},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2000},
    Month = {Oct},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2000/6422.html},
    Number = {UCB/CSD-00-1113},
    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.}
}

EndNote citation:

%0 Report
%A Su, Zhendong
%A Aiken, Alexander
%T Entailment with Conditional Equality Constraints (Extended Version)
%I EECS Department, University of California, Berkeley
%D 2000
%@ UCB/CSD-00-1113
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2000/6422.html
%F Su:CSD-00-1113