hide
Free keywords:
-
Abstract:
We show the NP-hardness of the satisfiability problem for subtype
inequalities between object types built by using simultaneously both
the functional and the record type constructors, without base types.
Earlier research concentrated on the complexity of subtyping either
solely functional, or solely record types. In both cases
deterministic cubic time algorithms are known.