MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2017

2. Number - only D2

MPI-I-98-2-004

Satisfiability of Functional+Record Subtype Constraints is NP-Hard

Vorobyov, Sergei

1998, 16 pages.

.
Status: available - back from printing

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.
Note:
To appear (in extended and revised form) in the Proceedings of the Annual Conference of the European Association for Computer Science Logic (CSl'98), August 22-28, 1998, Brno, Czech Republic. Springer Lecture Notes in Computer Science.

  • MPI-I-98-2-004.ps
  • Attachement: ATTE4TIK (234 KBytes)

URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-2-004

Hide details for BibTeXBibTeX
@TECHREPORT{Vorobyov98-2-004,
  AUTHOR = {Vorobyov, Sergei},
  TITLE = {Satisfiability of Functional+Record Subtype Constraints is NP-Hard},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-98-2-004},
  YEAR = {1998},
  ISSN = {0946-011X},
  NOTE = {To appear (in extended and revised form) in the Proceedings of the Annual Conference of the European Association for Computer Science Logic (CSl'98), August 22-28, 1998, Brno, Czech Republic. Springer Lecture Notes in Computer Science.},
}