Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-98-2-004

Satisfiability of Functional+Record Subtype Constraints is NP-Hard

Vorobyov, Sergei

MPI-I-98-2-004. 1998, 16 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-98-2-004.ps234 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
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.},
}