English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Report

Satisfiability of Functional+Record Subtype Constraints is NP-Hard

MPS-Authors
/persons/resource/persons45677

Vorobyov,  Sergei
Programming Logics, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

MPI-I-98-2-004.pdf
(Any fulltext), 254KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Vorobyov, S.(1998). Satisfiability of Functional+Record Subtype Constraints is NP-Hard (MPI-I-1998-2-004). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-7B51-7
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.