de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Satisfiability of Functional+Record Subtype Constraints is NP-Hard

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45677

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

Locator
There are no locators available
Fulltext (public)

1998-2-004
(Any fulltext), 10KB

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: http://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.