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.
-
- Attachement: ATTE4TIK (234 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-2-004
BibTeX
@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.},
}